B-деревья и b+trees только хранят данные в листах?
B деревья и b + деревья только хранят данные в своих листах? Я предполагаю, что они используют свои внутренние узлы для поиска необходимых данных.
Имеет место, что или они хранят данные в каждом узле?
2 ответа
«Записи» нелистовых узлов содержат
- указатель (своего рода «адрес» узла) на узел на следующем уровне вниз по дереву
- значение ключа первой (или последней, в зависимости от реализации) записи в этом узле
Такие нелистовые «записи» перечислены в порядке ключей, так что при сканировании (или двоичном поиске внутри) нелистовой узел, известно, какой узел на следующем нижнем уровне может содержать искомое значение.
Записи конечных узлов содержат полные записи данных: значение ключа и все остальное.
Следовательно, «настоящие» данные содержатся только в конечных узлах, а нелистовые узлы содержат только [копию] значений ключа. для очень небольшой части данных (эта пропорция зависит от среднего числа записей данных, найденных в листовом узле).
Это проиллюстрировано на следующем изображении из статьи Википедии о деревьях B +
Нелистовой узел наверху (единственный в этом упрощенном дереве) содержит только две записи нелистового узла. , каждый с копией ключевого значения (голубоватый цвет) и указателем на соответствующий узел (серый цвет). У этого дерева всего два уровня, поэтому «записи» в корневом узле указывают на листовые узлы. Можно представить, что есть дополнительные уровни (назовите его выше верхнего дерева, показанного ниже, "узел 3-5"); если бы это было так, вышеприведенный узел содержал бы (наряду с другими аналогичными записями) запись со значением ключа 3 с указателем на узел "3-5".
Также обратите внимание, что только значения ключей 3 и 5 содержатся в нелистовых узлах (т.е. даже не все значения ключей воспроизводятся в неконечных узлах).
Кстати, в этом примере нелистовые узлы содержат ключ последней записи в следующем узле (также будет работать, если использовалась первая запись вместо этого небольшая разница в способе реализации логики поиска).
Листовые узлы содержат значение ключа (тоже голубоватого цвета) и соответствующую запись данных (d1, d2 ... показаны серым). Красный указатель, показанный в конце каждого листового узла, указывает на следующий листовой узел, то есть тот, который содержит самую следующую запись данных в ключевом порядке; эти указатели полезны для «сканирования» ряда записей данных.