Я изучаю лучшие структуры данных для реализации простой временной базы данных объекта с открытым исходным кодом, и в настоящее время я очень люблю использовать для этого постоянные красно-черные деревья.
Моей основной причиной использования постоянных структур данных является, прежде всего, минимизация использования блокировок, поэтому база данных может быть как можно более параллельной. Также будет проще реализовать транзакции ACID и даже возможность абстрагировать базу данных для параллельной работы на кластере какого-либо типа.
Преимущество этого подхода заключается в том, что он позволяет реализовать временные базы данных практически бесплатно. И это очень приятно иметь, особенно для Интернета и анализа данных (например, тренды).
Все это очень круто, но я немного подозрительно отношусь к общей производительности использования постоянной структуры данных на диске. Несмотря на то, что сегодня есть несколько очень быстрых дисков, и все записи могут выполняться асинхронно, поэтому ответ всегда немедленный, я не хочу создавать все приложения с ложной предпосылкой, только чтобы понять, что это не очень хорошо способ сделать это.
Вот моя мысль:
- Поскольку все записи выполняются асинхронно, а использование постоянной структуры данных позволит не аннулировать предыдущую и действующую на данный момент структуру, время записи на самом деле не является узким местом.
- Существует некоторая литература по таким структурам, как this , предназначенная именно для использования диска. Но мне кажется, что эти методы добавят больше накладных расходов на чтение для ускорения записи. Но я думаю, что как раз наоборот предпочтительнее. Кроме того, многие из этих методов на самом деле приводят к множественным версиям деревьев, но они не являются строго неизменяемыми, что очень важно для оправдания постоянных накладных расходов.
- Я знаю, что при добавлении значений в базу данных все еще должна быть какая-то блокировка, и я также знаю, что должна быть хорошая логика сбора мусора, если не все версии будут поддерживаться (в противном случае размер файла, несомненно, резко возрастет) , Также можно подумать о системе дельта-сжатия.
- Из всех структур деревьев поиска я действительно считаю, что красно-черные наиболее близки к тому, что мне нужно, поскольку они предлагают наименьшее количество поворотов.
Но есть некоторые возможные подводные камни на этом пути:
- Асинхронные записи могут повлиять на приложения, которым нужны данные в режиме реального времени. Но я не думаю, что это имеет место с веб-приложениями, в большинстве случаев. Кроме того, когда требуются данные в реальном времени, могут быть разработаны другие решения, такие как система регистрации / извлечения конкретных данных, которые необходимо будет обрабатывать в режиме реального времени.
- Также они могут привести к некоторым конфликтам коммитов, хотя я не могу придумать хороший пример того, когда это может произойти. Также конфликты фиксации могут возникать в обычных СУБД, если два потока работают с одними и теми же данными, верно?
- Накладные расходы на наличие такого неизменяемого интерфейса будут расти в геометрической прогрессии, и скоро все обречено на провал, так что это плохая идея.
Есть мысли?
Спасибо!
редактирование:
Кажется, есть неправильное понимание того, что такое постоянная структура данных:
http://en.wikipedia.org/wiki/Persistent_data_structure