B+ дерево

B+ дерево
B+ дерево
Тип	Дерево (структура данных)
Операция
Временная сложность в обозначении большого О
Операция	Средний
Поиск	О( вход )
Вставлять	О( вход )
Удалить	О( вход )
Пространственная сложность
Космос	На )

Дерево B+ — это m-арное дерево с переменным, но часто большим количеством дочерних элементов на узел. Дерево B+ состоит из корня, внутренних узлов и листьев. ^{[ 1 ]} Корень может быть либо листом, либо узлом с двумя или более дочерними элементами.

Дерево B+ можно рассматривать как B-дерево , в котором каждый узел содержит только ключи (а не пары ключ-значение) и к которому внизу добавляется дополнительный уровень со связанными листьями.

Основная ценность дерева B+ заключается в хранении данных для эффективного извлечения в блочно-ориентированном контексте хранения, в частности в файловых системах . Это происходит главным образом потому, что в отличие от бинарных деревьев поиска деревья B+ имеют очень большое разветвление (количество указателей на дочерние узлы в узле, ^{[ 1 ]} обычно порядка 100 или более), что уменьшает количество операций ввода-вывода, необходимых для поиска элемента в дереве.

История

Не существует ни одной статьи, представляющей концепцию дерева B+. Вместо этого идея хранения всех данных в конечных узлах неоднократно упоминается как интересный вариант B-дерева, предложенный Р. Байером и Э. МакКрайтом. ^{[ 2 ]} Дуглас Комер в раннем обзоре B-деревьев (который также охватывает деревья B+) отмечает, что дерево B+ использовалось в программном обеспечении доступа к данным IBM VSAM , и ссылается на опубликованную IBM статью 1973 года. ^{[ 3 ]}

Структура

Структура указателя

Как и другие деревья, деревья B+ можно представить как совокупность узлов трех типов: корневых , внутренних (так называемых внутренних) и листовых . В деревьях B+ для этих узлов сохраняются следующие свойства:

Если ${\textstyle k_{i}}$ существует в любом узле B+-дерева, то $k_{i-1}$ существует в том узле, где $i\geq 1$ .
Все листовые узлы имеют одинаковое количество предков (т. е. все они находятся на одной и той же глубине).

Свойства указателей узлов суммированы в таблицах ниже:

$K$ : Максимальное количество потенциальных ключей поиска для каждого узла в дереве B+. (это значение постоянно по всему дереву).
$p_{i}$ : указатель на индекс узла, отсчитываемый от нуля. $i$ .
$k_{i}$ : ключ поиска по индексу узла, начинающемуся с нуля. $i$ .

Структура указателя внутреннего узла
$p_{0}$ когда $k_{0}$ существует	$p_{i}$ когда $k_{i-1}$ и $k_{i}$ существовать	$p_{i}$ когда $k_{i-1}$ существует, и $k_{i}$ не существует	$p_{i}$ когда $k_{i-1}$ и $k_{i}$ не существует
Указывает на поддерево, в котором все ключи поиска меньше $k_{0}$ .	Указывает на поддерево, в котором все ключи поиска больше или равны $k_{i-1}$ и меньше, чем $k_{i}$ .	Указывает на поддерево, в котором все ключи поиска больше или равны $k_{i-1}$ .	Здесь, $p_{i}$ пусто.

Структура указателя листового узла
$p_{i}$ когда $k_{i}$ существует	$p_{i}$ когда $k_{i}$ не существует и $i\neq K$	$p_{K}$
Указывает на запись со значением, равным $k_{i}$ .	Здесь, $p_{i}$ пусто.	Указывает на следующий лист дерева.

Границы узла

Границы узлов приведены в таблице ниже:

Тип узла	Минимальное количество ключей	Максимальное количество ключей	Минимальное количество дочерних узлов	Максимальное количество дочерних узлов
Корневой узел (если это листовой узел)	0	$K$	0	0
Корневой узел (если это внутренний узел)	1	$K$	2 ^{[ 1 ]}	$K+1$
Внутренний узел	$\lfloor K/2\rfloor$	$K$	$\lceil (K+1)/2\rceil$ $\equiv \lfloor K/2\rfloor +1$	$K+1$
Листовой узел	$\lceil K/2\rceil$	$K$	0	0

^{[ 4 ]}^{[ 5 ]}

Интервалы во внутренних узлах

Простой пример дерева B+, связывающий ключи 1–7 со значениями данных d ₁ -d ₇ . Связанный список (красный) позволяет быстро перемещаться по порядку. Коэффициент ветвления этого конкретного дерева равен $b$ =4. Оба ключа в листовом и внутреннем узлах здесь окрашены в серый цвет.

{\displaystyle б} — Простой пример дерева B+, связывающий ключи 1–7 со значениями данных d ₁ -d ₇ . Связанный список (красный) позволяет быстро перемещаться по порядку. Коэффициент ветвления этого конкретного дерева равен $b$ =4. Оба ключа в листовом и внутреннем узлах здесь окрашены в серый цвет.

По определению, каждое значение, содержащееся в дереве B+, является ключом, содержащимся ровно в одном листовом узле. Каждый ключ должен быть напрямую сопоставим с любым другим ключом, что формирует общий порядок . ^{[ 6 ]} Это позволяет каждому листовому узлу постоянно хранить все свои ключи отсортированными, что затем позволяет каждому внутреннему узлу создавать упорядоченный набор интервалов, представляющих непрерывную протяженность значений, содержащихся в данном листе. Внутренние узлы выше в дереве могут затем создавать свои собственные интервалы, которые рекурсивно объединяют интервалы, содержащиеся в их собственных дочерних внутренних узлах. В конце концов, корень дерева B+ представляет собой весь диапазон значений в дереве, где каждый внутренний узел представляет собой подинтервал.

Чтобы сохранить эту информацию о рекурсивном интервале, внутренние узлы должны дополнительно содержать $m-1$ копии ключей $l_{i}$ для $i\in [1,m-1]$ представляющий наименьший элемент в интервале, охватываемом дочерним элементом с индексом $i$ (который сам может быть внутренним узлом или листом). Где $m$ представляет фактическое количество дочерних элементов для данного внутреннего узла.

Характеристики

Коэффициент порядка или ветвления $b$ дерева B+ измеряет емкость внутренних узлов, то есть максимально допустимое количество прямых дочерних узлов. Это значение является постоянным для всего дерева. Для $h$ дерева B+ b-порядка с $уровнями$ индекса: ^{[ нужна ссылка ]}

Максимальное количество сохраняемых записей равно $n_{\max }=b^{h}-b^{h-1}$
Минимальное количество хранимых записей равно $n_{\min }=2\left\lceil {\tfrac {b}{2}}\right\rceil ^{h-1}-2\left\lceil {\tfrac {b}{2}}\right\rceil ^{h-2}$
Минимальное количество ключей $n_{\mathrm {kmin} }=2\left\lceil {\tfrac {b}{2}}\right\rceil ^{h-1}-1$
Максимальное количество ключей $n_{\mathrm {kmax} }=b^{h}-1$
Площадь, необходимая для хранения дерева, равна $O(n)$
Для вставки записи требуется $O(\log _{b}n)$ операции
Для поиска записи требуется $O(\log _{b}n)$ операции
Для удаления (ранее расположенной) записи требуется $O(\log _{b}n)$ операции
Выполнение запроса диапазона с k элементами, входящими в диапазон, требует $O(\log _{b}n+k)$ операции
Древовидная структура B+ расширяется/сжимается по мере увеличения/уменьшения количества записей . Ограничений на размер B+ деревьев нет. Таким образом, повышается удобство использования системы баз данных .
Любое изменение структуры не влияет на производительность благодаря сбалансированным свойствам дерева. ^{[ 7 ]}
Данные хранятся в конечных узлах, а большее разветвление внутренних узлов помогает уменьшить высоту дерева и, следовательно, сократить время поиска. В результате он хорошо работает на дополнительных устройствах хранения данных. ^{[ 8 ]}
Поиск становится чрезвычайно простым, поскольку все записи хранятся только в листовом узле и последовательно сортируются в связанном списке.
Мы можем получить поиск диапазона или частичный поиск, используя дерево B+. Это можно сделать проще и быстрее за счет обхода древовидной структуры. Благодаря этой особенности древовидная структура B+ применяется во многих методах поиска. ^{[ 7 ]}

Алгоритмы

Поиск

Мы ищем значение $k$ в дереве B+. Это означает, что начиная с корня мы ищем лист, который может содержать значение $k$ . На каждом узле мы выясняем, за каким внутренним узлом нам следует следовать. Внутренний узел дерева B+ имеет не более $m\leq b$ детей, где каждый из них представляет отдельный подинтервал. Мы выбираем соответствующего дочернего элемента с помощью линейного поиска по $m$ записей, затем, когда мы наконец добираемся до листа, мы выполняем линейный поиск по его $n$ элементам для поиска нужного ключа. Поскольку мы проходим только одну ветвь всех дочерних элементов на каждой ступеньке дерева, мы достигаем $O(\log N)$ время выполнения, где $N$ — общее количество ключей, хранящихся в листьях дерева B+. ^{[ 4 ]}

function search(k, root) is
    let leaf = leaf_search(k, root)
    for leaf_key in leaf.keys():
        if k = leaf_key:
             return true
    return false

function leaf_search(k, node) is
    if node is a leaf:
        return node
    let p = node.children()
    let l = node.left_sided_intervals()
    assert  $|p|=|l|+1$ 
    let m = p.len()
    for i from 1 to m - 1:
        if  $k\leq l[i]$ :
            return leaf_search(k, p[i])
    return leaf_search(k, p[m])

Обратите внимание, что этот псевдокод использует индексацию массива с отсчетом от 1.

Вставка

Выполните поиск, чтобы определить, в какой узел должна попасть новая запись.
Если узел не заполнен (не более $b-1$ записи после вставки), добавьте запись.
В противном случае перед вставкой новой записи
- Разделите узел.
  - исходный узел содержит ⎡(L+1)/2⎤ элементов
  - новый узел содержит ⎣(L+1)/2⎦ элементов
- Скопируйте ⎡(L+1)/2⎤-й ключ в родительский узел и вставьте новый узел в родительский.
- Повторяйте до тех пор, пока не будет найден родительский элемент, который не нужно разделять.
- Вставьте новую запись в новый узел.
Если корень разделяется, относитесь к нему так, как если бы он имел пустой родительский элемент, и разделите его, как описано выше.

Деревья B+ растут у корня, а не у листьев. ^{[ 1 ]}

Массовая загрузка

Имея набор записей данных, мы хотим создать индекс дерева B+ для некоторого ключевого поля. Один из подходов — вставить каждую запись в пустое дерево. Однако это довольно дорого, поскольку каждая запись требует от нас начинать с корня и спускаться до соответствующей конечной страницы. Эффективной альтернативой является использование массовой загрузки.

Первым шагом является сортировка записей данных по ключу поиска в порядке возрастания.
Мы выделяем пустую страницу, которая будет служить корнем, и вставляем в нее указатель на первую страницу записей.
Когда корень заполнен, мы разделяем его и создаем новую корневую страницу.
Продолжайте вставлять записи в самую правую индексную страницу чуть выше уровня листа, пока все записи не будут проиндексированы.

Примечание :

когда самая правая индексная страница над конечным уровнем заполняется, она разделяется;
это действие, в свою очередь, может привести к разделению самой правой страницы индекса на один шаг ближе к корню;
разделения происходят только на крайнем правом пути от корня до уровня листьев. ^{[ 9 ]}

Удаление

Целью алгоритма удаления является удаление нужного узла входа из древовидной структуры. Мы рекурсивно вызываем алгоритм удаления на соответствующем узле до тех пор, пока ни один узел не будет найден. Для каждого вызова функции мы перемещаемся, используя индекс для навигации, пока не найдем узел, не удалим его, а затем вернемся к корню.

В записи L, которую мы хотим удалить:

- Если L заполнен хотя бы наполовину, готово.

- Если L имеет только d-1 записей, попробуйте перераспределить, заимствовав у родственного узла (соседний узел с тем же родителем, что и L).

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

- Если перераспределение не удалось, объедините L и родственного брата. После слияния родительский узел обновляется путем удаления ключа индекса, указывающего на удаленную запись. Другими словами, если произошло слияние, необходимо удалить запись (указывающую на L или одноуровневый элемент) из родительского элемента L.

Примечание. Слияние может распространиться на корень, что означает уменьшение высоты. ^{[ 10 ]}

Выполнение

Листья (самые нижние индексные блоки) дерева B+ часто связаны друг с другом в связанном списке; это делает запросы диапазона или (упорядоченную) итерацию по блокам более простыми и эффективными (хотя вышеупомянутая верхняя граница может быть достигнута даже без этого добавления). Это существенно не увеличивает занимаемое пространство или уход за деревом. Это иллюстрирует одно из существенных преимуществ B+-дерева перед B-деревом; в B-дереве, поскольку не все ключи присутствуют в листьях, такой упорядоченный связанный список построить невозможно. Таким образом, B+дерево особенно полезно в качестве индекса системы базы данных , где данные обычно находятся на диске, поскольку оно позволяет B+дереву фактически обеспечивать эффективную структуру для размещения самих данных (это описано в разделе ^{[ 11 ]}^: 238 как индексная структура «Альтернатива 1»).

Если система хранения имеет размер блока B байт, а сохраняемые ключи имеют размер k, возможно, наиболее эффективным B+-деревом является то, в котором $b={\tfrac {B}{k}}-1$ . Хотя теоретически в одноразовом использовании нет необходимости, на практике зачастую индексные блоки занимают немного дополнительного места (например, ссылки на связанные списки в конечных блоках). Наличие индексного блока, который немного больше фактического блока системы хранения, приводит к значительному снижению производительности; поэтому предпочтительнее проявлять осторожность.

Если узлы дерева B+ организованы как массивы элементов, то вставка или удаление элемента может занять значительное время, поскольку в среднем придется сдвинуть половину массива. Чтобы решить эту проблему, элементы внутри узла можно организовать в виде двоичного дерева или дерева B+ вместо массива.

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

Эффективность использования пространства B+-деревьев можно повысить, используя некоторые методы сжатия. Одна из возможностей — использовать дельта-кодирование для сжатия ключей, хранящихся в каждом блоке. Для внутренних блоков экономия места может быть достигнута за счет сжатия ключей или указателей. Для строковых ключей пространство можно сэкономить, используя следующий метод: Обычно i -я запись внутреннего блока содержит первый ключ блока ⁠. $i+1$ ⁠ . Вместо хранения полного ключа мы могли бы хранить кратчайший префикс первого ключа блока ⁠ $i+1$ ⁠, который строго больше (в лексикографическом порядке), чем последний ключ блока i . Есть еще простой способ сжатия указателей: если предположить, что несколько последовательных блоков ⁠ $i,i+1,...i+k$ ⁠ хранятся последовательно, то достаточно хранить только указатель на первый блок и количество последовательных блоков.

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

Приложения

Файловые системы

Файловые системы ReiserFS ReFS , NSS , XFS , JFS , BFS и ; используют этот тип дерева для индексации метаданных BFS также использует деревья B+ для хранения каталогов. NTFS использует деревья B+ для индексации каталогов и метаданных, связанных с безопасностью. EXT4 использует деревья экстентов (модифицированная структура данных дерева B+) для индексации экстентов файлов. ^{[ 12 ]} APFS использует деревья B+ для хранения сопоставлений идентификаторов объектов файловой системы с их местоположениями на диске, а также для хранения записей файловой системы (включая каталоги), хотя конечные узлы этих деревьев не имеют одноуровневых указателей. ^{[ 13 ]}

Системы баз данных

Системы управления реляционными базами данных, такие как IBM Db2 , ^{[ 11 ]} Информикс , ^{[ 11 ]} Microsoft SQL-сервер , ^{[ 11 ]} Оракул 8 , ^{[ 11 ]} Сибас АСЭ , ^{[ 11 ]} и SQLite ^{[ 14 ]} поддерживают этот тип дерева для индексов таблиц, хотя каждая такая система реализует базовую древовидную структуру B+ с вариациями и расширениями. Многие системы управления базами данных NoSQL, такие как CouchDB. ^{[ 15 ]} и Токийский кабинет ^{[ 16 ]} также поддерживают этот тип дерева для доступа и хранения данных.

Поиск в многомерной базе данных объектов , сопоставимых с конкретным объектом запроса, является одной из наиболее часто используемых и, тем не менее, дорогостоящих процедур в таких системах. ^{[ нужна ссылка ]} В таких ситуациях продуктивным является поиск ближайшего соседа с использованием B+-дерева. ^{[ 17 ]}

iDistance

Дерево B+ эффективно используется для создания метода индексированного поиска, называемого iDistance. iDistance ищет k ближайших соседей (kNN) в метрических пространствах высокой размерности. Данные в этих многомерных пространствах делятся на основе стратегий пространства или разделов, и каждый раздел имеет значение индекса, близкое к разделу. Отсюда эти точки могут быть эффективно реализованы с использованием дерева B+, таким образом, запросы сопоставляются с поиском по одному измерению. Другими словами, технику iDistance можно рассматривать как способ ускорения последовательного сканирования. Вместо сканирования записей от начала до конца файла данных iDistance начинает сканирование с мест, где ближайшие соседи могут быть получены заранее с очень высокой вероятностью. ^{[ 18 ]}

NVRAM

Энергонезависимая память с произвольным доступом (NVRAM) использует древовидную структуру B+ в качестве основного метода доступа к памяти для системы Интернета вещей (IoT) из-за ее нестатического энергопотребления и высокой надежности ячейковой памяти. B+ может эффективно регулировать передачу данных в память. Более того, благодаря продвинутым стратегиям в отношении частот некоторых часто используемых листьев или эталонных точек дерево B+ показывает значительные результаты в увеличении срока службы систем баз данных. ^{[ 19 ]}

См. также

Ссылки

^ Перейти обратно: ^а ^б ^с ^д Навате, Рамез Эльмасри, Шамкант Б. (2010). Основы систем баз данных (6-е изд.). Река Аппер-Седл, Нью-Джерси: Pearson Education. стр. 100-1 652–660. ISBN 9780136086208 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Байер, Р.; МакКрайт, Э. (ноябрь 1970 г.). «Организация и ведение крупных упорядоченных индексов» . Материалы семинара ACM SIGFIDET (ныне SIGMOD) 1970 года по описанию данных, доступу и контролю - SIGFIDET '70 . стр. 107–141. дои : 10.1145/1734663.1734671 . ISBN 978-1-4503-7941-0 .
^ Комер, Дуглас (1979). «Вездесущее B-дерево» . Обзоры вычислительной техники ACM . 11 (2): 121–137. дои : 10.1145/356770.356776 . S2CID 101673 .
^ Перейти обратно: ^а ^б Поллари-Малми, Кертту. « Деревья B+» ( PDF) . Информатика, факультет естественных наук, Хельсинкский университет . п. 3. Архивировано из оригинала (PDF) 14 апреля 2021 г.
^ Зильбершац, Авраам; Корт, Генри Ф.; Сударшан, С. (2020). Концепции системы баз данных (Седьмое изд.). Нью-Йорк, штат Нью-Йорк: McGraw-Hill Education. ISBN 978-1-260-08450-4 .
^ Груст, Торстен (лето 2013 г.). " "Индексирование с древовидной структурой: ISAM и B+-деревья" " (PDF) . Логотип Университета Тюбингена, факультет компьютерных наук: системы баз данных . п. 84. Архивировано из оригинала (PDF) 31 октября 2020 г.
^ Перейти обратно: ^а ^б Цейтлер, Эрик; Риш, Торе (2010). «Масштабируемое разделение больших потоков данных» . Системы баз данных для продвинутых приложений . Конспекты лекций по информатике. Том. 5982. стр. 184–198. дои : 10.1007/978-3-642-12098-5_15 . ISBN 978-3-642-12097-8 .
^ Сюй, Чанг; Шу, Лидан; Чен, Банда; Ян, Ченг; Ху, Тяньлэй (2010). «Миграция обновлений: эффективное дерево B+ для флэш-хранилищ». Системы баз данных для продвинутых приложений . Конспекты лекций по информатике. Том. 5982. стр. 276–290. дои : 10.1007/978-3-642-12098-5_22 . ISBN 978-3-642-12097-8 .
^ «ECS 165B: Лекция 6 по внедрению системы баз данных» (PDF) . Департамент CS Калифорнийского университета в Дэвисе . 9 апреля 2010 г. стр. 21–23.
^ Рамакришнан, Рагху; Йоханнес Герке (2003). Системы управления базами данных (3-е изд.). Бостон: МакГроу Хилл. ISBN 0-07-246563-8 . OCLC 49977005 .
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж Рамакришнан Рагху, Герке Йоханнес - Системы управления базами данных, McGraw-Hill Higher Education (2000), 2-е издание (en), стр. 267
^ Джампаоло, Доминик (1999). Практическое проектирование файловой системы с помощью файловой системы Be (PDF) . Морган Кауфманн. ISBN 1-55860-497-9 . Архивировано из оригинала (PDF) 13 февраля 2017 г. Проверено 29 июля 2014 г.
^ «Б-деревья». Справочник по файловой системе Apple (PDF) . Apple Inc. 22 июня 2020 г. п. 122 . Проверено 10 марта 2021 г.
^ Обзор SQLite версии 3
^ Руководство CouchDB (см. примечание после третьего абзаца)
^ Справка Токийского кабинета министров. Архивировано 12 сентября 2009 г., в Wayback Machine.
^ Системы баз данных для продвинутых приложений . Япония. 2010. {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
^ Джагадиш, Х.В.; Оой, Бенг Чин; Тан, Киан-Ли; Ю, Цуй; Чжан, Жуй (июнь 2005 г.). «iDistance: адаптивный метод индексации на основе B+-дерева для поиска ближайшего соседа» . Транзакции ACM в системах баз данных . 30 (2): 364–397. дои : 10.1145/1071610.1071612 . ISSN 0362-5915 . S2CID 967678 .
^ Дхарамджит; Чен, Цзэн-И; Чанг, Юань-Хао; Ву, Чун-Фэн; Ли, Чи-Хенг; Ши, Вэй-Куан (декабрь 2021 г.). «Помимо сокращения записи: схема индексации B⁺-дерева с поддержкой выравнивания износа в архитектуре на основе NVRAM» . Транзакции IEEE по автоматизированному проектированию интегральных схем и систем . 40 (12): 2455–2466. дои : 10.1109/TCAD.2021.3049677 . ISSN 0278-0070 . S2CID 234157183 .

Внешние ссылки

Реализации

[Navathe-1] Перейти обратно: ^а ^б ^с ^д Навате, Рамез Эльмасри, Шамкант Б. (2010). Основы систем баз данных (6-е изд.). Река Аппер-Седл, Нью-Джерси: Pearson Education. стр. 100-1 652–660. ISBN 9780136086208 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )

[2] Байер, Р.; МакКрайт, Э. (ноябрь 1970 г.). «Организация и ведение крупных упорядоченных индексов» . Материалы семинара ACM SIGFIDET (ныне SIGMOD) 1970 года по описанию данных, доступу и контролю - SIGFIDET '70 . стр. 107–141. дои : 10.1145/1734663.1734671 . ISBN 978-1-4503-7941-0 .

[3] Комер, Дуглас (1979). «Вездесущее B-дерево» . Обзоры вычислительной техники ACM . 11 (2): 121–137. дои : 10.1145/356770.356776 . S2CID 101673 .

[algorithms-pdf-4] Перейти обратно: ^а ^б Поллари-Малми, Кертту. « Деревья B+» ( PDF) . Информатика, факультет естественных наук, Хельсинкский университет . п. 3. Архивировано из оригинала (PDF) 14 апреля 2021 г.

[5] Зильбершац, Авраам; Корт, Генри Ф.; Сударшан, С. (2020). Концепции системы баз данных (Седьмое изд.). Нью-Йорк, штат Нью-Йорк: McGraw-Hill Education. ISBN 978-1-260-08450-4 .

[total-order-6] Груст, Торстен (лето 2013 г.). " "Индексирование с древовидной структурой: ISAM и B+-деревья" " (PDF) . Логотип Университета Тюбингена, факультет компьютерных наук: системы баз данных . п. 84. Архивировано из оригинала (PDF) 31 октября 2020 г.

[:0-7] Перейти обратно: ^а ^б Цейтлер, Эрик; Риш, Торе (2010). «Масштабируемое разделение больших потоков данных» . Системы баз данных для продвинутых приложений . Конспекты лекций по информатике. Том. 5982. стр. 184–198. дои : 10.1007/978-3-642-12098-5_15 . ISBN 978-3-642-12097-8 .

[8] Сюй, Чанг; Шу, Лидан; Чен, Банда; Ян, Ченг; Ху, Тяньлэй (2010). «Миграция обновлений: эффективное дерево B+ для флэш-хранилищ». Системы баз данных для продвинутых приложений . Конспекты лекций по информатике. Том. 5982. стр. 276–290. дои : 10.1007/978-3-642-12098-5_22 . ISBN 978-3-642-12097-8 .

[9] «ECS 165B: Лекция 6 по внедрению системы баз данных» (PDF) . Департамент CS Калифорнийского университета в Дэвисе . 9 апреля 2010 г. стр. 21–23.

[10] Рамакришнан, Рагху; Йоханнес Герке (2003). Системы управления базами данных (3-е изд.). Бостон: МакГроу Хилл. ISBN 0-07-246563-8 . OCLC 49977005 .

[DMS-11] Перейти обратно: ^а ^б ^с ^д ^и ^ж Рамакришнан Рагху, Герке Йоханнес - Системы управления базами данных, McGraw-Hill Higher Education (2000), 2-е издание (en), стр. 267

[practical-book-12] Джампаоло, Доминик (1999). Практическое проектирование файловой системы с помощью файловой системы Be (PDF) . Морган Кауфманн. ISBN 1-55860-497-9 . Архивировано из оригинала (PDF) 13 февраля 2017 г. Проверено 29 июля 2014 г.

[13] «Б-деревья». Справочник по файловой системе Apple (PDF) . Apple Inc. 22 июня 2020 г. п. 122 . Проверено 10 марта 2021 г.

[SQLite-14] Обзор SQLite версии 3

[CouchDB-15] Руководство CouchDB (см. примечание после третьего абзаца)

[TC-16] Справка Токийского кабинета министров. Архивировано 12 сентября 2009 г., в Wayback Machine.

[17] Системы баз данных для продвинутых приложений . Япония. 2010. {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

[18] Джагадиш, Х.В.; Оой, Бенг Чин; Тан, Киан-Ли; Ю, Цуй; Чжан, Жуй (июнь 2005 г.). «iDistance: адаптивный метод индексации на основе B+-дерева для поиска ближайшего соседа» . Транзакции ACM в системах баз данных . 30 (2): 364–397. дои : 10.1145/1071610.1071612 . ISSN 0362-5915 . S2CID 967678 .

[19] Дхарамджит; Чен, Цзэн-И; Чанг, Юань-Хао; Ву, Чун-Фэн; Ли, Чи-Хенг; Ши, Вэй-Куан (декабрь 2021 г.). «Помимо сокращения записи: схема индексации B⁺-дерева с поддержкой выравнивания износа в архитектуре на основе NVRAM» . Транзакции IEEE по автоматизированному проектированию интегральных схем и систем . 40 (12): 2455–2466. дои : 10.1109/TCAD.2021.3049677 . ISSN 0278-0070 . S2CID 234157183 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

v т и Древовидные структуры данных
Search trees (dynamic sets/associative arrays)	2–3 2–3–4 AA (a,b) AVL B B+ B* B^x (Optimal) Binary search Dancing HTree Interval Order statistic Palindrome (Left-leaning) Red–black Scapegoat Splay T Treap UB Weight-balanced
Heaps	Binary Binomial Brodal d-ary Fibonacci Leftist Pairing Skew binomial Skew van Emde Boas Weak
Tries	Ctrie C-trie (compressed ADT) Hash Radix Suffix Ternary search X-fast Y-fast
Spatial data partitioning trees	Ball BK BSP Cartesian Hilbert R k-d (implicit k-d) M Metric MVP Octree PH Priority R Quad R R+ R* Segment VP X
Other trees	Cover Exponential Fenwick Finger Fractal tree index Fusion Hash calendar iDistance K-ary Left-child right-sibling Link/cut Log-structured merge Merkle PQ Range SPQR Top