Как данные организованы в файле данных БД

Question

В качестве учебного упражнения я пытаюсь написать простую встроенную базу данных на C #.Все идет хорошо, но я действительно застреваю, когда дело доходит до сохранения данных на диск.

В качестве примера одной из моих проблем ... Возможно, мне нужно «вставить» данные в середину данныхфайл.Это явно невозможно при последовательном доступе к файлам.Переписывать всю последнюю половину файла каждый раз, когда происходит вставка, не представляется возможным по очевидным причинам производительности.

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

Я предполагаю, что мои вопросы ... именно так выглядят данные ""внутри файла данных типичной БД?Как / где новые данные записываются в файл?

Answer 1

Как правило, базы данных будут использовать B-дерево для хранения данных (где ключ будет первичным ключом строки, а значение будет содержимым строки) и индексов.Таким образом, вы можете вставлять строки в произвольные местоположения за O(log n) время.

Например, смотрите формат файла для баз данных SQLite , который описывает, как SQLite использует B-дерево, где только внутренние узлыуказатели и листовые узлы хранят только данные.

См. также: http://en.wikipedia.org/wiki/B-tree#Insertions_and_deletions_cause_trouble, что, похоже, решает проблему, с которой вы столкнулись.

Answer 2

Ответ Дэвида Вулевер неверен. Данные базы данных не хранятся в B-деревьях. B-деревья (обычно B + -деревья) хранят только ключи и дочерние указатели во внутренних узлах, а ключи и указатели данных в конечных узлах. Деревья B + обычно не хранят данные (они могут сделать это для таблиц отношений). Данные базы данных хранятся в файлах данных, которые организованы в блоки.