Что такое страница B-дерева

Question

Я думаю, что знаю, что такое B-дерево, но что такое страница B-дерева?

Answer 1

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

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

Например, если файловая система, естественно, работает с 16-килобайтными блоками данных, и если размер записей в B-дереве равен 500 b (включая ссылки на следующий уровень узлов), то 32 записи могут сохраняться в узле, делая размер узла равным размеру страницы и позволяя оптимизировать обращения к диску.

Answer 2

B-tree - это дерево с n-арностью, поэтому страница представляет собой именно «n» ячейки для размещения элементов из текущего узла и ссылки на них. Для дерева B + это может быть как мета-узлы (которые содержат только ссылки), так и листовые узлы для хранения данных.