Больше, чем структуры данных памяти и как они обычно обрабатываются

Question

Скажем, у меня есть структура данных на основе файлов, такая как B + Tree. Насколько я понимаю, данные, как ожидается, будут храниться на диске, но индекс обычно загружается в память. Что если у вас такой большой файл, что даже его индекс не помещается в память? Как это обычно обрабатывается? Во-вторых, поскольку индекс представляет собой дерево, а не линейный набор данных, как он обычно размещается на диске?

Мне в основном любопытно, как это делается в реальных проектах (таких как Berkeley DB). Очевидно, меня интересуют широкие мазки. Я надеюсь получить представление, поэтому у меня есть некоторый контекст, когда я копаюсь в разделе B-Tree моей книги по базе данных (или пробуждаю память из CS XYZ много лет назад)

Answer 1

B-деревья предназначены для систем на основе страниц, где данный узел вписывается в страницу. Чтобы найти запись в B-дереве, необходимо загружать только одну страницу за раз, так что вы можете сделать это.

Даже для их обновления не требуется, чтобы в памяти одновременно находилось большое количество страниц. Я полагаю, что наиболее сложной операцией является удаление, когда реорганизуются узлы, но если оно реализовано тщательно, то это можно сделать с относительно несколько страниц в памяти.

Answer 2

Чтобы ответить на ваш первый вопрос, структура данных, которая слишком велика для размещения в памяти, обычно делится на «страницы», обычно все страницы имеют одинаковый размер, и каждая страница содержит часть структуры данных, чтобы использовать данные, которые вы загружать и выгружать страницы.

Другим распространенным вариантом (который обычно не используется в СУБД, но часто встречается в таких вещах, как XML и медиа-файлы) является потоковая передача, при которой данные обрабатываются по порядку путем загрузки следующего раздела и удаления предыдущего.

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

Answer 3

Возможно, вы захотите взглянуть на SQLite . кодовая база намного меньше, чем Berkeley DB, это общественное достояние, она очень четко организована и прокомментирована, а документация вне источника превосходна. Научил меня много о деревьях в реальном мире