Rivalry2

HTML Diff

0 added 8 removed

Original 2026-01-01

Modified 2026-02-26

1 Ранее в курсе мы уже познакомились со сбалансированными деревьями поиска - это АВЛ-деревья или красно-черные деревья.

2 Они способны организовать эффективный поиск элементов за время logN. Но чтобы совершить этот поиск, потребуется выполнить logN операций. Со временем число данных, которые нужно хранить в дереве, будет расти. Дерево потребуется сохранять на более дешевых хранилищах данных вроде жестких дисков, а не хранить в оперативной памяти.

3 Это ведет к тому, что для поиска элемента в дереве нам придется logN раз обратиться к жесткому диску. При больших N это число операций остается существенным. Операции над жестким диском гораздо медленнее, чем над оперативной памятью. Значит, оборудование будет быстро изнашиваться, а само приложение будет работать медленнее.

4 Ученым предстояло решить, как организовать эффективный поиск в древовидных структурах, которые должны храниться в постоянной памяти. Чтобы решить эту задачу, они придумали новый вид деревьев - сильноветвящиеся B-деревья и их производные: B+ деревья, B*-деревья, 2-3 деревья.

5 В этом уроке мы детально познакомимся с видами сильноветвящихся деревьев и особенностями реализации операций поиска, вставки и удаления узлов.

6 <h2>Устройство B-деревьев</h2>

7 Рассмотрим дерево, которое состоит из миллиона элементов. Если хранить данные в сбалансированном бинарном дереве поиска, то поиск элемента займет двадцать операций:

8 log2(1000000) = 19,932

9 Если разбить дерево на страницы, в каждой из которых будет по семь узлов дерева, поиск поддерева с нужным элементом будет выполнен за семь обращений к диску:

10 log(7+1) 1000000 = 6,644

11 Рассмотрим пример такого разбиения:

12 Такая группировка узлов на страницах превращает бинарное дерево в октарное - с восемью дочерними узлами. Число дочерних узлов у страницы может и дальше увеличиваться, например, до 128 элементов. Это приведет к тому, что поиск элемента будет выполнен всего за три обращения к диску:

13 log128(1000000) = 2,847

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

15 В этом случае в узлах располагается несколько ключей в порядке возрастания слева направо. Дочерние узлы содержат ключи, которые находятся в промежутке между значениями родительского узла.

16 Помимо особенности расположения ключей стоит отметить, что B-дерево со степенью m обладает следующими свойствами:

17 <ul><li>Глубина всех листьев одинакова</li>

18 <li>Каждый узел имеет не более m потомков</li>

19 <li>Каждый узел кроме корневого и листовых имеют не менее m/2 потомков</li>

20 <li>Если высота дерева больше единицы, то у корневого узла не менее двух дочерних узлов</li>

21 <li>Нелистовой узел с k потомками имеет k-1 ключей</li>

22 </ul>Представим узел B-дерева в виде кода на JavaScript:

23 - Javascript

24 - Java

25 - Python

26 - PHP

27 Над B-деревьями выполняются все классические операции:

23 Над B-деревьями выполняются все классические операции:

28 <ul><li>Поиск узла</li>

24 <ul><li>Поиск узла</li>

29 <li>Добавление узла</li>

25 <li>Добавление узла</li>

30 <li>Удаление узла</li>

26 <li>Удаление узла</li>

31 </ul>Однако сложная организация ветвления узлов вносит свои реализации. Далее рассмотрим эти операции подробнее.

27 </ul>Однако сложная организация ветвления узлов вносит свои реализации. Далее рассмотрим эти операции подробнее.

32 <h2>Операции над B-деревьями</h2>

28 <h2>Операции над B-деревьями</h2>

33 Поиск узлов в случае работы с B-деревом отличается от аналогичной операции над бинарным деревом только порядком действий во время проверки ключей узла. Он будет выглядеть следующим образом:

29 Поиск узлов в случае работы с B-деревом отличается от аналогичной операции над бинарным деревом только порядком действий во время проверки ключей узла. Он будет выглядеть следующим образом:

34 - Javascript

35 - Java

36 - Python

37 - PHP

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

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

39 Вставка новых элементов в B-дерево разрешается только в листовые узлы. Это приводит к необходимости следить за заполненностью узлов. Если при вставке превысилась максимальная степень узла, то узел нужно разделять на части.

31 Вставка новых элементов в B-дерево разрешается только в листовые узлы. Это приводит к необходимости следить за заполненностью узлов. Если при вставке превысилась максимальная степень узла, то узел нужно разделять на части.

40 Чтобы разделить узел, создается два новых листовых узла, которые содержат половину значений из существующего узла, и переносится среднее значение в родительский узел.

32 Чтобы разделить узел, создается два новых листовых узла, которые содержат половину значений из существующего узла, и переносится среднее значение в родительский узел.

41 Если заполнен и корневой узел, то мы разбиваем его на два новых: выбираем среднее значение, создаем для него новый узел, который станет новым корнем всего дерева:

33 Если заполнен и корневой узел, то мы разбиваем его на два новых: выбираем среднее значение, создаем для него новый узел, который станет новым корнем всего дерева:

42 В данном примере мы вставляем ключ 3 в дерево с одним заполненным корневым узлом. Вставка ключа приводит к переполнению корневого узла. Чтобы решить эту ситуацию, мы разбиваем корневой узел на две части, создаем новый узел со средним значением и делаем его корнем всего дерева.

34 В данном примере мы вставляем ключ 3 в дерево с одним заполненным корневым узлом. Вставка ключа приводит к переполнению корневого узла. Чтобы решить эту ситуацию, мы разбиваем корневой узел на две части, создаем новый узел со средним значением и делаем его корнем всего дерева.

43 Аналогично изменение структуры узлов может возникнуть, когда узел удаляется. Если в соседних узлах слишком мало ключей - занятость узлов падает ниже значения m/2 - и эти узлы находятся на одном родственном уровне, то такие узлы необходимо слить. Данная ситуация называетсяантипереполнением.

35 Аналогично изменение структуры узлов может возникнуть, когда узел удаляется. Если в соседних узлах слишком мало ключей - занятость узлов падает ниже значения m/2 - и эти узлы находятся на одном родственном уровне, то такие узлы необходимо слить. Данная ситуация называетсяантипереполнением.

44 Существует два способа объединения узлов:

36 Существует два способа объединения узлов:

45 <ul><li>Если у двух смежных узлов общий предок, и их содержимые помещаются в один узел, их следует объединить</li>

37 <ul><li>Если у двух смежных узлов общий предок, и их содержимые помещаются в один узел, их следует объединить</li>

46 <li>Если содержимое смежных узлов не помещается в одном узле, то ключи перераспределяются между ними, чтобы восстановить баланс</li>

38 <li>Если содержимое смежных узлов не помещается в одном узле, то ключи перераспределяются между ними, чтобы восстановить баланс</li>

47 </ul>Операции слияния и расщепления достаточно дорогостоящие. Чтобы оптимизировать данный процесс, были придуманы специальные подвиды B-деревьев.

39 </ul>Операции слияния и расщепления достаточно дорогостоящие. Чтобы оптимизировать данный процесс, были придуманы специальные подвиды B-деревьев.

48 <h2>Производные виды деревьев</h2>

40 <h2>Производные виды деревьев</h2>

49 К производным видам B-деревьев чаще всего относят следующие три вида:

41 К производным видам B-деревьев чаще всего относят следующие три вида:

50 <ul><li>B⁺-деревья</li>

42 <ul><li>B⁺-деревья</li>

51 <li>B*-деревья</li>

43 <li>B*-деревья</li>

52 <li>2-3-деревья</li>

44 <li>2-3-деревья</li>

53 </ul><h3>B⁺-деревья</h3>

45 </ul><h3>B⁺-деревья</h3>

54 В B⁺-деревьях данные ключей хранятся только в листовых узлах, а в промежуточных хранятся копии значений ключей. Это помогает эффективно организовывать поиск в блочных средах хранения. Например, в файловых системах, где B⁺-деревья применяют, чтобы хранить каталоги.

46 В B⁺-деревьях данные ключей хранятся только в листовых узлах, а в промежуточных хранятся копии значений ключей. Это помогает эффективно организовывать поиск в блочных средах хранения. Например, в файловых системах, где B⁺-деревья применяют, чтобы хранить каталоги.

55 Также реляционные системы управления базами данных, такие как DB2, Informix, Microsoft SQL Server, Oracle, поддерживают этот тип деревьев, чтобы организовывать табличные индексы.

47 Также реляционные системы управления базами данных, такие как DB2, Informix, Microsoft SQL Server, Oracle, поддерживают этот тип деревьев, чтобы организовывать табличные индексы.

56 <h3>B*-деревья</h3>

48 <h3>B*-деревья</h3>

57 B*-дерево ориентировано на более плотное хранение ключей во внутренних узлах. Этот вариант гарантирует, что некорневые узлы заполнены как минимум на две трети от m вместо половины от m.

49 B*-дерево ориентировано на более плотное хранение ключей во внутренних узлах. Этот вариант гарантирует, что некорневые узлы заполнены как минимум на две трети от m вместо половины от m.

58 B*-деревья используются для того, чтобы вызывать дорогостоящую операцию разделения как можно реже. Чтобы достичь этого, вместо немедленного разделения узла при его заполнении, его ключи "переливаются" в соседний узел. Если же и соседний узел заполнен, то ключи приблизительно поровну разделяются на три новых узла.

50 B*-деревья используются для того, чтобы вызывать дорогостоящую операцию разделения как можно реже. Чтобы достичь этого, вместо немедленного разделения узла при его заполнении, его ключи "переливаются" в соседний узел. Если же и соседний узел заполнен, то ключи приблизительно поровну разделяются на три новых узла.

59 <h3>2-3-деревья</h3>

51 <h3>2-3-деревья</h3>

60 2-3 деревья - частный случай B⁺-деревьев с сокращенным количеством элементов на страницах. Каждый узел 2-3-дерева, кроме листовых, может содержать только один ключ и два потомка, либо два ключа и три потомка.

52 2-3 деревья - частный случай B⁺-деревьев с сокращенным количеством элементов на страницах. Каждый узел 2-3-дерева, кроме листовых, может содержать только один ключ и два потомка, либо два ключа и три потомка.

61 <h2>Выводы</h2>

53 <h2>Выводы</h2>

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

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

63 Для оптимизации хранения и поиска данных в таких условиях были предложены B-деревья. Они помогают сократить нагрузку на диск. Это возможно, если увеличить количество веток в узлах и хранить несколько ключей полезной нагрузки.

55 Для оптимизации хранения и поиска данных в таких условиях были предложены B-деревья. Они помогают сократить нагрузку на диск. Это возможно, если увеличить количество веток в узлах и хранить несколько ключей полезной нагрузки.