Алгоритм на псевдокоде. Поиск в Б – дереве (D: Данные, a: pPage)

19 20 21 22 23 24 25

Поиск в Б – дереве (D: Данные, a: pPage)

Обозначим L, R левая и правая границы поиска на странице

IF (a = NIL) (Ключа D нет в дереве)

ELSE L:= 1, R:= k + 1

DO (L < R)

i:= [(L + R)/2]

IF (a→e_i.data ≤ D) L:= i + 1

ELSE R:= i

R:= R – 1

IF (R > 0 и a→e_R.data = D) (ключ D есть в дереве)

ELSE (на этой странице ключа D нет)

IF (R = 0) Поиск в Б-дереве (D, a→p₀)

ELSE Поиск в Б-дереве (D, a→e_R.p)

13.3 Построение Б-дерева

Построение Б-дерева или включение нового элемента данных D в Б-дерево происходит следующим образом:

· Выполним поиск элемента D в дереве.

· Если элемента D нет в дереве, то мы имеем страницу a и позицию R, в которой ожидали найти элемент D.

· Вставим элемент в позицию R+1, при этом количество элементов на странице k увеличилось на 1.

· Если k < = 2 m, то процесс включения закончен.

· Если k > 2 m (переполнение страницы), то создаём новую страницу b, переносим в неё m правых элементов из страницы a, а средний элемент переносим на один уровень вверх на родительскую страницу.

· Включение элемента в родительскую страницу производится по такому же алгоритму.

· Если родительской страницы нет, то она создаётся и в неё включается один элемент.

Эта схема сохраняет все характерные свойства Б-дерева. Получившиеся две новые страницы содержат ровно по m элементов. Включение элемента в родительскую страницу может опять перевести к переполнению, то есть разделение страниц может распространиться до самого корня. В этом случае может увеличиться высота дерева. Таким образом, Б-деревья растут обратно: от листа к корню.

Пример построения Б-дерева при m = 2. Предварительно удалим повторяющиеся буквы.