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


B-дерево

Перевод
B-дерево
B-дерево
Тип Дерево
Изобретено в 1972 году
Изобретено Rudolf Bayer, Edward M. McCreight
Временная сложность
в О-символике
В среднем В худшем случае
Расход памяти O(n) O(n)
Поиск O(log n) O(log n)
Вставка O(log n) O(log n)
Удаление O(log n) O(log n)
Пример B-дерева степени 2

B-дерево (по-русски произносится как Б-дерево) — структура данных, дерево поиска. С точки зрения внешнего логического представления, сбалансированное, сильно ветвистое дерево во внешней памяти.

Использование B-деревьев впервые было предложено Р. Бэйером (англ. R. Bayer) и Е. МакКрейтом (англ. E. McCreight) в 1970 году.

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

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

С точки зрения физической организации B-дерево представляется как мультисписочная структура страниц внешней памяти, то есть каждому узлу дерева соответствует блок внешней памяти (страница). Внутренние и листовые страницы обычно имеют разную структуру.

Содержание

Применение

Структура B-дерева применяется для организации индексов во многих современных СУБД.

B-дерево может применяться для структурирования (индексирования) информации на жёстком диске (как правило, метаданных). Время доступа к произвольному блоку на жёстком диске очень велико (порядка миллисекунд), поскольку оно определяется скоростью вращения диска и перемещения головок. Поэтому важно уменьшить количество узлов, просматриваемых при каждой операции. Использование поиска по списку каждый раз для нахождения случайного блока могло бы привести к чрезмерному количеству обращений к диску, вследствие необходимости осуществления последовательного прохода по всем его элементам, предшествующим заданному; тогда как поиск в B-дереве, благодаря свойствам сбалансированности и высокой ветвистости, позволяет значительно сократить количество таких операций.

Относительно простая реализация алгоритмов и существование готовых библиотек (в том числе для C) для работы со структурой B-дерева обеспечивают популярность применения такой организации памяти в самых разнообразных программах, работающих с большими объёмами данных.

Структура и принципы построения

B-деревом называется дерево, удовлетворяющее следующим свойствам:

  1. Каждый узел содержит хотя бы один ключ. Ключи в каждом узле упорядочены. Корень содержит от 1 до 2t-1 ключей. Любой другой узел содержит от t-1 до 2t-1 ключей. Листья не являются исключением из этого правила. Здесь t - параметр дерева, не меньший 2 (и обычно принимающий значения от 50 до 2000[1]).
  2. Любой узел кроме листа, содержащий ключи K_1, ..., K_n, содержит n+1 сыновей. При этом
    1. Первый сын и все его потомки содержат ключи из интервала (-\infty, K_1)
    2. Для 2\le i\le n, i-й сын и все его потомки содержат ключи из интервала (K_{i-1}, K_i)
    3. (n+1)-й сын и все его потомки содержат ключи из интервала (K_n, \infty)
  3. Глубина всех листьев одинакова.

Свойство 2 можно сформулировать иначе: каждый узел B-дерева, кроме листьев, можно рассматривать как упорядоченный список, в котором чередуются ключи и указатели на сыновей.

Поиск

Если ключ содержится в корне, он найден. Иначе определяем интервал и идём к соответствующему сыну. Повторяем, пока не дошли до листа.

Добавление ключа

Будем называть деревом потомков некоего узла поддерево, состоящее из этого узла и его потомков.

Вначале определим функцию, которая добавляет ключ K к дереву потомков узла x. После выполнения функции во всех пройденных узлах, кроме, может быть, самого узла x, будет меньше 2t-1, но не меньше t-1, ключей.

  1. Если х - не лист,
    1. Определяем интервал, где должен находиться K. Пусть y - соответствующий сын.
    2. Рекурсивно добавляем K к дереву потомков y.
    3. Если узел y полон, то есть содержит 2t-1 ключей, расщепляем его на два. Узел y_1 получает первые t-1 из ключей y и первые t его потомков, а узел y_2 - последние t-1 из ключей y и последние t его потомков. Медианный из ключей узла y попадает в узел х, а указатель на y в узле x заменяется указателями на узлы y_1 и y_2.
  2. Если x - лист, просто добавляем туда ключ K.

Теперь определим добавление ключа K ко всему дереву. Буквой R обозначается корневой узел.

  1. Добавим K к дереву потомков R.
  2. Если R содержит теперь 2t-1 ключей, расщепляем его на два. Узел R_1 получает первые t-1 из ключей R и первые t его потомков, а узел R_2 - последние t-1 из ключей R и последние t его потомков. Медианный из ключей узла R попадает вo вновь созданный узел, который становится корневым. Узлы R_1 и R_2 становятся его потомками.

Удаление ключа

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

Если x - лист, удаляем оттуда ключ. Если в узле x осталось не меньше t-1 ключей, мы на этом останавливаемся. Иначе мы смотрим на количество ключей в следующем, а потом в предыдущем узле. Если следующий узел есть, и в нём не менее t ключей, мы добавляем в x ключ-разделитель между ним и следующим узлом, а на его место ставим первый ключ следующего узла, после чего останавливаемся. Если это не так, но есть предыдущий узел, и в нём не менее t ключей, мы добавляем в x ключ-разделитель между ним и предыдущим узлом, а на его место ставим последний ключ предыдущего узла, после чего останавливаемся. Наконец, если и с предыдущим ключом не получилось, мы объединяем узел x со следующим или предыдущим узлом, и в объединённый узел перемещаем ключ, разделяющий два узла. При этом в родительском узле может остаться только t-2 ключей. Тогда, если это не корень, мы выполняем аналогичную процедуру с ним. Если мы в результате дошли до корня, и в нём осталось от 1 до t-1 ключей, делать ничего не надо, потому что корень может иметь и меньше t-1 ключей. Если же в корне не осталось ни одного ключа, исключаем корневой узел, а его единственный потомок делаем новым корнем дерева.

Если x - не лист, а K - его i-й ключ, удаляем самый правый ключ из поддерева потомков i-го сына x, или, наоборот, самый левый ключ из поддерева потомков i+1-го сына x. После этого заменяем ключ K удалённым ключом. Удаление ключа происходит так, как описано в предыдущем абзаце.

Основные достоинства

  • Во всех случаях полезное использование пространства вторичной памяти составляет свыше 50 %. С ростом степени полезного использования памяти не происходит снижения качества обслуживания.
  • Произвольный доступ к записи реализуется посредством малого количества подопераций (обращения к физическим блокам).
  • В среднем достаточно эффективно реализуются операции включения и удаления записей; при этом сохраняется естественный порядок ключей с целью последовательной обработки, а также соответствующий баланс дерева для обеспечения быстрой произвольной выборки.
  • Неизменная упорядоченность по ключу обеспечивает возможность эффективной пакетной обработки.

Основной недостаток В-деревьев состоит в отсутствии для них эффективных средств выборки данных (т.е. метода обхода дерева), упорядоченных по отличному от выбранного ключу.

См. также

Литература

  • Ананий В. Левитин. Глава 7. Пространственно-временной компромисс: B-деревья // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Algorithms. — М.: Вильямс, 2006. — С. 331—339. — ISBN 0-201-74395-7
  • Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Глава 18. B-деревья // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: Вильямс, 2006. — С. 515­—536. — ISBN 0-07-013151-1

Ссылки

Примечания

  1. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Глава 18. B-деревья // Алгоритмы: построение и анализ = Introduction to Algorithms. — 2-е изд. — М.: Вильямс, 2006. — С. 515­—536. — ISBN 0-07-013151-1



Wikimedia Foundation. 2010.

См. также в других словарях:

  • B*-дерево — B* дерево  разновидность B дерева, в которой каждый узел дерева заполнен не менее чем на 2/3 (в отличие от B дерева, где этот показатель составляет 1/2). B+ дерево, удовлетворяющее таким требованиям называется B+* деревом. B* деревья… …   Википедия

  • B+ дерево — Пример B+ дерева, связывающего ключи 1 7 с данными d1 d7. Связи (выделены красным) позволяют быстро обходить дерево в порядке возрастания ключей. B+ дерево  структура данных, представляет собой сбалансированное дерево поиска. Яв …   Википедия

  • Дерево отрезков — структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов массива. Содержание 1 Дерево отрезков в памяти …   Википедия

  • Дерево Фенвика — (двоичное индексированное дерево, англ. Fenwick tree, binary indexed tree, BIT) структура данных, позволяющая быстро изменять значения в массиве и находить некоторые функции от элементов массива. Впервые описано Питером Фенвиком в 1994 году …   Википедия

  • Дерево Фибоначчи — АВЛ дерево с наименьшим числом вершин при заданной высоте (глубине). Если для какой либо из вершин высота поддерева, для которого эта вершина является корнем, равна , то правое и левое поддерево этой вершины имеют высоты равные соответственно и …   Википедия

  • B+-деревья — A simple B+ tree example linking the keys 1 7 to data values d1 d7. Note the linked list (red) allowing rapid in order traversal. B+ дерево  структура данных, представляет собой дерево поиска. Является модификацией B дерева, истинные… …   Википедия

  • B+ деревья — A simple B+ tree example linking the keys 1–7 to data values d1 d7. Note the linked list (red) allowing rapid in order traversal. B+ дерево это B дерево, истинные значения ключей которого содержатся только в листьях, а не в листьях ключи… …   Википедия

  • Дерево (структура данных) — У этого термина существуют и другие значения, см. Дерево (значения). Простой пример неупорядоченного дерева Дерево  одна из наиболее широко распространённых структу …   Википедия

  • Дерево (теория графов) — У этого термина существуют и другие значения, см. Дерево (значения). Дерево  это связный ациклический граф.[1] Связность означает наличие путей между любой парой вершин, ацикличность  отсутствие циклов и то, что между парами вершин… …   Википедия

  • Дерево квадрантов — Разбитая с помощью дерева квадрантов плоскость Дерево квадрантов (также квадродерево, 4 дерево, англ. quadtree) дере …   Википедия

Фильмы

  • Рожденные Октябрем., 1977 — Через судьбы конкретных героев фильм рассказывает о достижениях страны, прошедшей 60-летний путь после победы Великой Октябрьской социалистической революции.
  • Борис Пророков., 1977 — Произведения, дневники, воспоминания художника. Рассказывается о творчестве Лауреата Ленинской премии Бориса Ивановича Пророкова.
  • Либретто одной жизни., 1989 — Исповедь человека, прошедшего трудными дорогами войны в Афганистане.

Книги

Другие книги по запросу «B-дерево» >>