Структуры данных, используемые в СУБД

Question

Какая структура данных используется в СУБД, такой как Oracle, MySQL и Sqlite, для хранения и извлечения записей.

Answer 1

Обычно умная реализация B-Trees

Из вышеупомянутой связанной статьи в википедии:

B-дерево порядка m (максимальное число дочерних элементов для каждого узла) - это дерево, которое удовлетворяет следующим свойствам:

1. Каждый узел имеет не более m дочерних элементов.
2. Каждый узел (кроме корня и листьев) имеет по крайней мере 2 детей.
3. Корень имеет как минимум двух дочерних элементов, если это не листовой узел.
4. Все листья появляются на одном уровне и несут информацию.
5. Неконечный узел с k дочерними элементами содержит k – 1 ключ

Преимущества в том, что к данным можно получить доступ в логарифмическом времени, как и в большинстве деревьев поиска (таких как стандартные двоичные деревья), но свойства синхронизации лучше в среднем случае.

Answer 2

MySQL имеет подключаемые системы хранения. Это означает, что двигатель может использовать разные хранилища. В настоящее время есть 5-6 из них, которые вы можете использовать. И так как это с открытым исходным кодом, вы можете увидеть, как это делается.

SQLite использует собственную реализацию B-Tree с журналированием. Открытый исходный код - вы можете посмотреть на него.

Firebird и Interbase используют B-Trees с системами контроля версий с несколькими записями для хранения. Firebird с открытым исходным кодом. Стоит посмотреть.

Невозможно определить для Oracle , MS SQL Server или других проприетарных систем баз данных, поскольку они хранят информацию о хранилище в секрете.