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

СВ: /* Источники */

2026-10-31T22:25:31Z

Источники

← Предыдущая		Версия 22:25, 31 октября 2026
Строка 558:		Строка 558:
	# Comer D. The Ubiquitous B-Tree // ACM Computing Surveys. — 1979. — Vol. 11, No. 2. — P. 121–137.		# Comer D. The Ubiquitous B-Tree // ACM Computing Surveys. — 1979. — Vol. 11, No. 2. — P. 121–137.
	# Wikipedia: B-tree (варианты B*). URL: https://en.wikipedia.org/wiki/B-tree.		# Wikipedia: B-tree (варианты B*). URL: https://en.wikipedia.org/wiki/B-tree.

			[[Category:Алгоритмы и структуры данных]]
			[[Category:Деревья поиска]]

СВ: /* Связанные темы */

2026-10-31T21:00:35Z

Связанные темы

← Предыдущая		Версия 21:00, 31 октября 2026
Строка 547:		Строка 547:
	* [[B-дерево]] — базовое многопутевое дерево.		* [[B-дерево]] — базовое многопутевое дерево.
	* [[B+-дерево]] — вариант с данными в листьях; B*-политика к нему применима.		* [[B+-дерево]] — вариант с данными в листьях; B*-политика к нему применима.
	* [[2-3 дерево]] — минимальный пример многоключевых узлов.		* [[2-3-дерево]] — минимальный пример многоключевых узлов.
	* [[Асимптотическая сложность]] — нотация <math>O</math>, <math>\Omega</math>, <math>\Theta</math>.		* [[Асимптотическая сложность]] — нотация <math>O</math>, <math>\Omega</math>, <math>\Theta</math>.

СВ: /* Связанные темы */

2026-10-31T21:00:18Z

Связанные темы

← Предыдущая		Версия 21:00, 31 октября 2026
Строка 546:		Строка 546:

	* [[B-дерево]] — базовое многопутевое дерево.		* [[B-дерево]] — базовое многопутевое дерево.
	* [[B⁺-дерево]] — вариант с данными в листьях; B*-политика к нему применима.		* [[B+-дерево]] — вариант с данными в листьях; B*-политика к нему применима.
	* [[2-3 дерево]] — минимальный пример многоключевых узлов.		* [[2-3 дерево]] — минимальный пример многоключевых узлов.
	* [[Асимптотическая сложность]] — нотация <math>O</math>, <math>\Omega</math>, <math>\Theta</math>.		* [[Асимптотическая сложность]] — нотация <math>O</math>, <math>\Omega</math>, <math>\Theta</math>.

СВ: /* Задачи для практики */

2026-10-31T21:00:06Z

Задачи для практики

← Предыдущая		Версия 21:00, 31 октября 2026
Строка 538:		Строка 538:
	# '''Удаление.''' Реализуйте перераспределение и слияние при недостаче. Подсказка: порог <math>\lceil 2m/3\rceil</math>.		# '''Удаление.''' Реализуйте перераспределение и слияние при недостаче. Подсказка: порог <math>\lceil 2m/3\rceil</math>.
	# '''Высота.''' Постройте деревья, дающие крайние высоты; сравните с оценками <math>\log_4 N+1</math> и <math>\log_6 N+1</math> при <math>m=8</math>. Подсказка: все узлы по 3 ключа против всех по 5.		# '''Высота.''' Постройте деревья, дающие крайние высоты; сравните с оценками <math>\log_4 N+1</math> и <math>\log_6 N+1</math> при <math>m=8</math>. Подсказка: все узлы по 3 ключа против всех по 5.
	# '''B*-политика на B⁺.''' Добавьте redistribute/2-to-3 к [[B⁺-дерево\|B⁺-дереву]] и измерьте занятость листьев. Подсказка: разделители — копии.		# '''B*-политика на B⁺.''' Добавьте redistribute/2-to-3 к [[B+-дерево\|B⁺-дереву]] и измерьте занятость листьев. Подсказка: разделители — копии.
	# '''Число расщеплений.''' Сравните суммарное число расщеплений у B и B* для <math>n=10^6</math>. Подсказка: считайте вызовы split.		# '''Число расщеплений.''' Сравните суммарное число расщеплений у B и B* для <math>n=10^6</math>. Подсказка: считайте вызовы split.
	# '''Большой порядок.''' Повторите измерение занятости при <math>m = 32, 64, 128</math> и покажите сходимость к 2/3. Подсказка: малый <math>m</math> искажает гарантию.		# '''Большой порядок.''' Повторите измерение занятости при <math>m = 32, 64, 128</math> и покажите сходимость к 2/3. Подсказка: малый <math>m</math> искажает гарантию.

СВ: /* Типичные ошибки и подводные камни */

2026-10-31T20:59:54Z

Типичные ошибки и подводные камни

← Предыдущая		Версия 20:59, 31 октября 2026
Строка 521:		Строка 521:
	== Типичные ошибки и подводные камни ==		== Типичные ошибки и подводные камни ==

	* '''Путаница с [[B⁺-дерево\|B⁺-деревом]].''' B* задаёт '''занятость''' и способ расщепления; B⁺ — где лежат данные. Их можно совместить.		* '''Путаница с [[B+-дерево\|B⁺-деревом]].''' B* задаёт '''занятость''' и способ расщепления; B⁺ — где лежат данные. Их можно совместить.
	* '''Расщеплять раньше времени.''' Сначала нужно попробовать redistribute с соседом; расщепление — только когда оба соседа полны.		* '''Расщеплять раньше времени.''' Сначала нужно попробовать redistribute с соседом; расщепление — только когда оба соседа полны.
	* '''Неверный 2-to-3 split.''' Объединяются '''два узла и разделитель''', делятся на три; в родителя уходят '''два''' разделителя — легко забыть второй.		* '''Неверный 2-to-3 split.''' Объединяются '''два узла и разделитель''', делятся на три; в родителя уходят '''два''' разделителя — легко забыть второй.

СВ: /* TL;DR */

2026-10-31T20:59:27Z

TL;DR

← Предыдущая		Версия 20:59, 31 октября 2026
Строка 1:		Строка 1:
	== TL;DR ==		== TL;DR ==

	B-дерево (B-star tree) — вариант B-дерева, в котором узлы держат '''повышенную минимальную занятость: не менее двух третей''' (у обычного [[B-дерево\|B-дерева]] — не менее половины). Ключевое отличие в поведении при переполнении: прежде чем расщеплять узел, ключи пытаются '''перераспределить''' с соседним узлом (redistribute); расщепление делают только тогда, когда '''оба''' соседних узла полны, и тогда делят сразу '''два узла на три''' (2-to-3 split), поднимая в родителя два разделителя. Это уменьшает число узлов и расщеплений и снижает высоту дерева (гарантия <math>h \le \log_{\lceil 2m/3\rceil} N + 1</math> вместо <math>\log_{\lceil m/2\rceil} N + 1</math>), но усложняет реализацию: приходится следить сразу за двумя соседями. B-политику применяют и к B-деревьям, и к [[B⁺-дерево\|B⁺-деревьям]].		B-дерево (B-star tree) — вариант B-дерева, в котором узлы держат '''повышенную минимальную занятость: не менее двух третей''' (у обычного [[B-дерево\|B-дерева]] — не менее половины). Ключевое отличие в поведении при переполнении: прежде чем расщеплять узел, ключи пытаются '''перераспределить''' с соседним узлом (redistribute); расщепление делают только тогда, когда '''оба''' соседних узла полны, и тогда делят сразу '''два узла на три''' (2-to-3 split), поднимая в родителя два разделителя. Это уменьшает число узлов и расщеплений и снижает высоту дерева (гарантия <math>h \le \log_{\lceil 2m/3\rceil} N + 1</math> вместо <math>\log_{\lceil m/2\rceil} N + 1</math>), но усложняет реализацию: приходится следить сразу за двумя соседями. B-политику применяют и к B-деревьям, и к [[B+-дерево\|B⁺-деревьям]].

	{\| class="wikitable"		{\| class="wikitable"
Строка 23:		Строка 23:
	\| Память \|\| <math>O(N)</math>; узлы заполнены плотнее → меньше страниц		\| Память \|\| <math>O(N)</math>; узлы заполнены плотнее → меньше страниц
	\|-		\|-
	\| Варианты \|\| B*-дерево на основе [[B-дерево\|B-дерева]] и [[B⁺-дерево\|B⁺-дерева]]		\| Варианты \|\| B*-дерево на основе [[B-дерево\|B-дерева]] и [[B+-дерево\|B⁺-дерева]]
	\|-		\|-
	\| Где встречается \|\| системы, где важны плотность хранения и редкие расщепления; учебные и СУБД/ФС-реализации		\| Где встречается \|\| системы, где важны плотность хранения и редкие расщепления; учебные и СУБД/ФС-реализации

СВ: Новая страница: «== TL;DR == B*-дерево (B-star tree) — вариант B-дерева, в котором узлы держат '''повышенную минимальну...»

2026-10-31T20:58:45Z

Новая страница: «== TL;DR == B*-дерево (B-star tree) — вариант B-дерева, в котором узлы держат '''повышенную минимальну...»

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