|
|
|
B+-деревья
Схема организации классических B-деревьев не очень хороша для практического использования, т.к. возможен набор проблем:
- Возможен большой объем записей, что приводит к тому, что внутренние страницы не могут содержать много элементов и увеличение глубины дерева.
- Необходимость хранения данных переменной длины
Широкое практическое применение получила модификация механизма B-деревьев, которую принято называть B+-деревьями. Внутренние страницы устроены так же, как у B-дерева, но в них хранятся только ключи (без записей) и ссылки на страницы-потомки. В листовых страницах хранятся все ключи, содержащиеся в дереве, вместе с записями, причём этот список упорядочен по возрастанию значения ключа.
экономного и сбалансированного использования внешней памяти при реализации B+-деревьев иногда используют технику слияния трёх соседних страниц в две и расщепления двух соседних страниц в три. Дополнительной полезной оптимизацией B+-деревьев является связывание листовых страниц в одно- или двунаправленный список. Это позволяет просматривать списки записей для заданного диапазона значений ключей с лишь одним прохождением дерева от корня к листу.
|
