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