В-деревья

В-дерево – это особый вид сбалансированного m -арного дерева, который позволяет выполнять операции поиска, вставки и удаления записей из внешнего файла с гарантированной производительностью для самой неблагоприятной ситуации.

В-дерево порядка m представляет собой m -арное дерево поиска, характеризующееся следующими свойствами.

1. Корень либо является листом, либо имеет хотя бы двух сыновей.

2. Каждый узел, за исключением корня и листьев, имеет от m/2 до m сыновей.

3. Все пути от корня до любого листа имеют одинаковую длину.

На рис. 52 показано В-дерево порядка 5, здесь предполагается, что в блоке листа помещается не более трех записей.

Рис. 52 – В-дерево порядка 5

В-дерево можно рассматривать как иерархический индекс, каждый узел в котором занимает блок во внешней памяти. Корень В-дерева является индексом первого уровня. Каждый нелистовой узел на В-дереве имеет форму где является указателем на i -ого сына, а – ключ, Ключи в узле упорядочены, поэтому Все ключи в поддереве, на которое указывает , меньше, чем . В случае все ключи в поддереве, на которое указывает , имеют значения, не меньшие, чем , и меньшие, чем Все ключи в поддереве, на которое указывает , имеют значения, не меньшие, чем .

Существует несколько способов организации листьев. В данном случае предполагается, что записи основного файла хранятся только в листьях, и каждый лист занимает один блок.

Дата добавления: 2015-07-16