B-дерево - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:33:23Z

rollbackEdits.php mass rollback

88.208.225.209 в 04:22, 1 сентября 2022

2022-09-01T04:22:20Z

Михаил: /* Удаление ключа из листа */ "Удалим из исходного узла лист" -> "Удалим из исходного узла ключ"

2020-06-26T08:51:30Z

‎Удаление ключа из листа: "Удалим из исходного узла лист" -> "Удалим из исходного узла ключ"

Mervap: /* Вариации B-дерева */

2018-04-17T21:59:39Z

‎Вариации B-дерева

Mervap: /* См. также */

2018-04-17T21:58:49Z

‎См. также

Mervap: /* Разбиение узла */

2018-04-17T21:54:28Z

‎Разбиение узла

Mervap в 21:53, 17 апреля 2018

2018-04-17T21:53:46Z

Mervap в 21:51, 17 апреля 2018

2018-04-17T21:51:25Z

Внесённые изменения

Lapenok.aleksej в 10:37, 1 апреля 2018

2018-04-01T10:37:35Z

Внесённые изменения

Maksnov в 13:22, 8 июня 2015

2015-06-08T13:22:54Z

← Предыдущая		Версия 16:33, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	'''B-дерево''' (англ. ''B-tree'') {{---}} сильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за <tex>O(\log n)</tex>. B-дерево с <tex>n</tex> узлами имеет высоту <tex>O(\log n)</tex>. Количество детей узлов может быть от нескольких до тысяч (обычно степень ветвления B-дерева определяется характеристиками устройства (дисков), на котором производится работа с деревом). В-деревья также могут использоваться для реализации многих операций над динамическими множествами за время <tex>O(\log n)</tex>		'''B-дерево''' (англ. ''B-tree'') {{---}} сильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за <tex>O(\log n)</tex>. B-дерево с <tex>n</tex> узлами имеет высоту <tex>O(\log n)</tex>. Количество детей узлов может быть от нескольких до тысяч (обычно степень ветвления B-дерева определяется характеристиками устройства (дисков), на котором производится работа с деревом). В-деревья также могут использоваться для реализации многих операций над динамическими множествами за время <tex>O(\log n)</tex>

← Предыдущая		Версия 04:22, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	'''B-дерево''' (англ. ''B-tree'') {{---}} сильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за <tex>O(\log n)</tex>. B-дерево с <tex>n</tex> узлами имеет высоту <tex>O(\log n)</tex>. Количество детей узлов может быть от нескольких до тысяч (обычно степень ветвления B-дерева определяется характеристиками устройства (дисков), на котором производится работа с деревом). В-деревья также могут использоваться для реализации многих операций над динамическими множествами за время <tex>O(\log n)</tex>		'''B-дерево''' (англ. ''B-tree'') {{---}} сильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за <tex>O(\log n)</tex>. B-дерево с <tex>n</tex> узлами имеет высоту <tex>O(\log n)</tex>. Количество детей узлов может быть от нескольких до тысяч (обычно степень ветвления B-дерева определяется характеристиками устройства (дисков), на котором производится работа с деревом). В-деревья также могут использоваться для реализации многих операций над динамическими множествами за время <tex>O(\log n)</tex>

@@ Строка 137: / Строка 137: @@
 [[Файл:B3dell.PNG|550px|Удаление <tex>F</tex> из листа]]
-В противном случае, если существует соседний лист с тем же родителем, который содержит больше <tex>t - 1</tex> ключа, выберем ключ-разделитель из соседа разделяющий оставшиеся ключи соседа и ключи исходного узла (то есть не больше всех из одной группы и не меньше всех из другой). Обозначим этот ключ как <tex>k_1</tex>. Выберем другой ключ из родительского узла, разделяющий исходный узел и его соседа, который был выбран ранее. Этот ключ обозначим <tex>k_2</tex>. Удалим из исходного узла лист, который нужно было удалить, спустим в этот узел <tex>k_2</tex>, а вместо <tex>k_2</tex> в родительском узле поставим <tex>k_1</tex>. Если все соседи содержат по <tex>t - 1</tex> ключу, то [[B-дерево#.D0.A1.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5|объединяем]] узел с каким-либо из соседей, удаляем ключ, и ключ из родительского узла, который был разделителем разделённых соседей, [[B-дерево#.D0.9F.D0.B5.D1.80.D0.B5.D0.BC.D0.B5.D1.89.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BA.D0.BB.D1.8E.D1.87.D0.B0|переместим]] в новый узел.
+В противном случае, если существует соседний лист с тем же родителем, который содержит больше <tex>t - 1</tex> ключа, выберем ключ-разделитель из соседа разделяющий оставшиеся ключи соседа и ключи исходного узла (то есть не больше всех из одной группы и не меньше всех из другой). Обозначим этот ключ как <tex>k_1</tex>. Выберем другой ключ из родительского узла, разделяющий исходный узел и его соседа, который был выбран ранее. Этот ключ обозначим <tex>k_2</tex>. Удалим из исходного узла ключ, который нужно было удалить, спустим в этот узел <tex>k_2</tex>, а вместо <tex>k_2</tex> в родительском узле поставим <tex>k_1</tex>. Если все соседи содержат по <tex>t - 1</tex> ключу, то [[B-дерево#.D0.A1.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5|объединяем]] узел с каким-либо из соседей, удаляем ключ, и ключ из родительского узла, который был разделителем разделённых соседей, [[B-дерево#.D0.9F.D0.B5.D1.80.D0.B5.D0.BC.D0.B5.D1.89.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BA.D0.BB.D1.8E.D1.87.D0.B0|переместим]] в новый узел.
 ==== Удаление ключа из внутреннего узла ====

@@ Строка 160: / Строка 160: @@
 == Вариации B-дерева ==
 === B+-дерево ===
-В B-дереве вместе с ключом может храниться только указатель на другую дисковую страницу, содержащую сопутствующую информацию для данного ключа. Существует распространённая модификация B-дерева, называемая B+-деревом, в которой, вся сопутствующая информация хранится в листьях, а во внутренних узлах хранятся только ключи и указатели на дочерние узлы. Таким образом удается получить максимально возможную степень ветвления во внутренних узлах.
+В B-дереве вместе с ключом может храниться только указатель на другую дисковую страницу, содержащую сопутствующую информацию для данного ключа. Существует распространённая модификация B-дерева, называемая [[B+-дерево|B+-деревом]], в которой, вся сопутствующая информация хранится в листьях, а во внутренних узлах хранятся только ключи и указатели на дочерние узлы. Таким образом удается получить максимально возможную степень ветвления во внутренних узлах.
 === B*-дерево ===

@@ Строка 170: / Строка 170: @@
 == См. также ==
 * [[2-3 дерево]]
 * [[Splay-дерево]]
 * [[АВЛ-дерево]]

@@ Строка 105: / Строка 105: @@
 Функция <tex>\operatorname{B-Tree-Split-Child}</tex> получает в качестве входного параметра незаполненный внутренний узел <tex>x</tex> (находящийся в оперативной памяти), индекс <tex>t</tex> и узел <tex>y</tex> (также находящийся в оперативной памяти), такой что <tex>y = c_i[x]</tex> является заполненным дочерним узлом <tex>x</tex>. Процедура разбивает дочерний узел на два и соответствующим образом обновляет поля <tex>x</tex>, внося в него информацию о новом дочернем узле. Для разбиения заполненного корневого узла мы сначала делаем корень дочерним узлом нового пустого корневого узла, после чего можно вызвать функцию. При этом высота дерева увеличивается на <tex>1</tex>. Отметим, что увеличить высоту B-дерева можно только разбиением.
-[[Файл:B3splt.PNG|550px|Разбиение узла B-дерева с <tex>t=4</tex>]]
+[[Файл:B3splt.PNG|550px|Разбиение узла B-дерева с t=4]]
   '''void''' B-Tree-Split-Child(x: '''Node''', t: '''int''', i: '''int'''):
@@ Строка 128: / Строка 128: @@
       Disk-Write(z)
       Disk-Write(x)
 === Удаление ключа ===

@@ Строка 1: / Строка 1: @@
-'''B-дерево''' (англ. ''B-tree'') {{---}} сильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за <tex>O(\log n)</tex>. B-дерево с <tex><n/tex> узлами имеет высоту <tex>O(\log n)</tex>. Количество детей узлов может быть от нескольких до тысяч (обычно степень ветвления B-дерева определяется характеристиками устройства (дисков), на котором производится работа с деревом). В-деревья также могут использоваться для реализации многих операций над динамическими множествами за время <tex>O(\log n)</tex>
+'''B-дерево''' (англ. ''B-tree'') {{---}} сильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за <tex>O(\log n)</tex>. B-дерево с <tex>n</tex> узлами имеет высоту <tex>O(\log n)</tex>. Количество детей узлов может быть от нескольких до тысяч (обычно степень ветвления B-дерева определяется характеристиками устройства (дисков), на котором производится работа с деревом). В-деревья также могут использоваться для реализации многих операций над динамическими множествами за время <tex>O(\log n)</tex>
 B-дерево было впервые предложено Р. Бэйером и Е. МакКрейтом в <tex>1970</tex> году.
@@ Строка 55: / Строка 55: @@
 === Добавление ключа ===
 Ищем лист, в который можно добавить ключ, совершая проход от корня к листьям. Если найденный узел незаполнен, добавляем в него ключ. Иначе разбиваем узел на два узла, в первый добавляем первые <tex>t - 1</tex> ключей, во второй — последние <tex>t - 1</tex> ключей. После добавляем ключ в один из этих узлов. Оставшийся средний элемент добавляется в родительский узел, где становится разделительной точкой для двух новых поддеревьев.
-[[Файл:B3inssp.png|550px|Разбиение корня с <tex>t = 4</tex>. Корневой узел <tex>r</tex> разделяется на два узла, и создаётся новый корень <tex>s</tex>. Новый корень содержит средний ключ <tex>r</tex> и две половины <tex>r</tex> в качестве детей. Разбиением узла высота дерева увеличивается на единицу]]
+[[Файл:B3inssp.png|550px|Разбиение корня с t = 4. Корневой узел r разделяется на два узла, и создаётся новый корень s. Новый корень содержит средний ключ r и две половины r в качестве детей. Разбиением узла высота дерева увеличивается на единицу]]
 Если и родительский узел заполнен — повторяем пока не встретим незаполненный узел или не дойдем до корня. В последнем случае корень разбивается на два узла и высота дерева увеличивается.
@@ Строка 144: / Строка 144: @@
 Рассмотрим удаление из внутреннего узла. Имеется внутренний узел <tex>x</tex> и ключ, который нужно удалить, <tex>k</tex>. Если дочерний узел, предшествующий ключу <tex>k</tex>, содержит больше <tex>t - 1</tex> ключа, то находим <tex>k_1</tex> – предшественника <tex>k</tex> в поддереве этого узла. Удаляем его. Заменяем <tex>k</tex> в исходном узле на <tex>k_1</tex>. Проделываем аналогичную работу, если дочерний узел, следующий за ключом <tex>k</tex>, имеет больше <tex>t - 1</tex> ключа. Если оба (следующий и предшествующий дочерние узлы) имеют по <tex>t - 1</tex> ключу, то [[B-дерево#.D0.A1.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5|объединяем]] этих детей, [[B-дерево#.D0.9F.D0.B5.D1.80.D0.B5.D0.BC.D0.B5.D1.89.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BA.D0.BB.D1.8E.D1.87.D0.B0|переносим]] в них <tex>k</tex>, а далее удаляем <tex>k</tex> из нового узла. Если [[B-дерево#.D0.A1.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5|сливаются]] <tex>2</tex> последних потомка корня – то они становятся корнем, а предыдущий корень освобождается.
-[[Файл:B3delin.png|550px|Удаление <tex>M</tex> и <tex>G</tex> из внутренних узлов]]
+[[Файл:B3delin.png|550px|Удаление M и G из внутренних узлов]]
 ==== Перемещение ключа ====

@@ Строка 1: / Строка 1: @@
-<wikitex>'''B-дерево''' — сильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за $O(\log n)$. B-дерево с $n$ узлами имеет высоту $O(\log n)$. Количество детей узлов может быть от нескольких до тысяч (обычно степень ветвления B-дерева определяется характеристиками устройства (дисков), на котором производится работа с деревом). В-деревья также могут использоваться для реализации многих операций над динамическими множествами за время $O(\log n)$
+<wikitex>'''B-дерево''' (англ. ''B-tree'') {{---}} сильноветвящееся сбалансированное дерево поиска, позволяющее проводить поиск, добавление и удаление элементов за $O(\log n)$. B-дерево с $n$ узлами имеет высоту $O(\log n)$. Количество детей узлов может быть от нескольких до тысяч (обычно степень ветвления B-дерева определяется характеристиками устройства (дисков), на котором производится работа с деревом). В-деревья также могут использоваться для реализации многих операций над динамическими множествами за время $O(\log n)$
 B-дерево было впервые предложено Р. Бэйером и Е. МакКрейтом в 1970 году.</wikitex>
@@ Строка 19: / Строка 19: @@
      '''Node''' c[] <span style="color:#008000">    // указатели на детей узла</span>
 === Структура дерева ===
-  '''struct''' B-tree
+  '''struct''' BTree
      '''int'''  t <span style="color:#008000">      // минимальная степень дерева</span>
      '''Node''' root <span style="color:#008000">   // указатель на корень дерева</span>
@@ Строка 32: / Строка 32: @@
 Система в состоянии поддерживать в процессе работы в оперативной памяти только ограниченное количество страниц. Мы будем считать, что страницы, которые более не используются, удаляются из оперативной памяти системой; наши алгоритмы работы с В-деревьями не будут заниматься этим самостоятельно. Поскольку в большинстве систем время выполнения алгоритма, работающего с В-деревьями, зависит в первую очередь от количества выполняемых операций чтения/записи с диском, желательно минимизировать их количество и за один раз считывать и записывать как можно больше информации. Таким образом, размер узла В-дерева обычно соответствует дисковой странице. Количество потомков узла В-дерева, таким образом, ограничивается размером дисковой страницы.
-Для больших В-деревьев, хранящихся на диске, степень ветвления обычно находится между 50 и 2000, в зависимости от размера ключа относительно размера страницы. Большая степень ветвления резко снижает как высоту дерева, так и количество обращений к диску для поиска ключа. Например, если есть миллиард ключей, и $t=1001$, то поиск ключа займёт две дисковые операции. </wikitex>
+Для больших В-деревьев, хранящихся на диске, степень ветвления обычно находится между <tex>50</tex> и <tex>2000</tex>, в зависимости от размера ключа относительно размера страницы. Большая степень ветвления резко снижает как высоту дерева, так и количество обращений к диску для поиска ключа. Например, если есть миллиард ключей, и $t=1001$, то поиск ключа займёт две дисковые операции. </wikitex>
 == Высота ==
@@ Строка 62: / Строка 62: @@
 Вставка ключа в B-дерево $T$ высоты $h$ за один нисходящий проход по дереву потребует $O(h)$ обращений к диску и $O(th)=O(t \log_t n)$ процессорного времени.
 <code>
-  '''void''' B-Tree-Insert(T, k)
+  '''void''' B-Tree-Insert(T: '''BTree''', k: '''int'''):
       r = T.root
-      '''if''' r.n == 2t - 1
+      '''if''' r.n == 2T.t - 1
           s = Allocate-Node()
           T.root = s
-          s.leaf = false
+          s.leaf = ''false''
           s.n = 0
           s.c[1] = r
-          B-Tree-Split-Child(s, 1)
+          B-Tree-Split-Child(s, T.t, 1)
-          B-Tree-Insert-Nonfull(s, k)
+          B-Tree-Insert-Nonfull(s, k, T.t)
       '''else'''
-          B-Tree-Insert-Nonfull(r, k)
+          B-Tree-Insert-Nonfull(r, k, T.t)
 </code>
 <code>
-  '''void''' B-Tree-Insert-Nonfull(x, k)
+  '''void''' B-Tree-Insert-Nonfull(x: '''Node''', k: '''int''', t: '''int'''):
       i = x.n
       '''if''' x.leaf
@@ Строка 91: / Строка 91: @@
           Disk-Read(x.c[i])
           '''if''' x.c[i].n == 2t - 1
-              B-Tree-Split-Child(x, i)
+              B-Tree-Split-Child(x, t, i)
               '''if''' k > x.key[i]
                   i = i + 1
-          B-Tree-Insert-Nonfull(x.c[i], k)
+          B-Tree-Insert-Nonfull(x.c[i], k, t)
 </code>
 Функция $\operatorname{B-Tree-Insert-Nonfull}$ вставляет ключ $k$ в узел $x$, который должен быть незаполненным при вызове.
@@ Строка 107: / Строка 107: @@
 [[Файл:B3splt.PNG|550px|Разбиение узла B-дерева с t=4]]
 <code>
-  '''void''' B-Tree-Split-Child(x, i)
+  '''void''' B-Tree-Split-Child(x: '''Node''', t: '''int''', i: '''int'''):
       z = Allocate-Node()
       y = x.c[i]
@@ Строка 186: / Строка 186: @@
 [[Категория:Дискретная математика и алгоритмы]]
 [[Категория:Деревья поиска]]