Когда B-дерево используется на диске, оно не считывается из файла, десериализуется, модифицируется, сериализуется и записывается обратно.
B-дерево на диске - это структура данных на основе дискасостоящий из блоков данных, и эти блоки читаются и записываются по одному блоку за раз.Обычно:
- Каждый узел в B-дереве представляет собой блок данных (байты).Блоки имеют фиксированные размеры.
- Блоки адресуются по их позиции в файле, если файл используется, или по адресу их сектора, если блоки B-Tree отображаются непосредственно в сектора диска.
- «Указатель на дочерний узел» - это просто число, которое является адресом блока узла.
- Блоки большие.Как правило, достаточно большой, чтобы иметь 1000 детей и более.Это потому, что чтение блока стоит дорого, но стоимость не сильно зависит от размера блока.Сохраняя блоки достаточно большими, чтобы во всем дереве было только 3 или 4 уровня, мы минимизируем количество операций чтения или записи, необходимых для доступа к какому-либо конкретному элементу.
- Кэширование обычно используется так, что большинству обращений требуется толькочтобы коснуться самого нижнего уровня дерева на диске.
Таким образом, чтобы найти элемент в B-дереве, вы должны прочитать корневой блок (он, вероятно, выйдет из кеша), просмотреть егочтобы найти соответствующий дочерний блок и прочитать его (опять, вероятно, из кэша), возможно, сделайте это снова, наконец, прочитайте соответствующий листовой блок и извлеките данные.