B+-дерево — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «'''B+-дерево''' (англ. ''B+-tree'') {{---}} структура данных на основе B-дерева, сбалансиров…»)
 
Строка 2: Строка 2:
  
 
== Где используется ==
 
== Где используется ==
Изначально структура предназначалась для хранения данных в целях эффективного поиска в блочно-ориентированной среде хранения в частности, для файловых систем. Структура широко применяется в файловых системах NTFS, ReiserFS, NSS, XFS, JFS, ReFS и BFS используют этот тип дерева для индексирования метаданных; BeFS также использует B+‍‍-деревья для хранения каталогов. Реляционные системы управления базами данных, такие как DB2, Informix, Microsoft SQL Server, Oracle Database (начиная с версии 8), Adaptive Server Enterprise и SQLite поддерживают этот тип деревьев для табличных индексов. Среди NoSQL-СУБД, работающих с моделью «ключ—значение», структура данных реализована для доступа к данным в CouchDB, MongoDB (при использовании подсистемы хранения WiredTiger[en]) и Tokyo Cabinet[en].
+
Изначально структура предназначалась для эффективного поиска в блочно-ориентированной среде хранения {{---}} в частности, для файловых систем. Структура широко применяется в таких файловых системах, как NTFS<ref>[[wikipedia:NTFS |Wikipedia {{---}} NTFS]]</ref>, ReiserFS<ref>[[wikipedia:ReiserFS |Wikipedia {{---}} ReiserFS]]</ref>, NSS<ref>[[wikipedia:Novell Storage Services |Wikipedia {{---}} NSS]]</ref>, JFS<ref>[[wikipedia:JFS (file system) |Wikipedia {{---}} JFS]]</ref>, ReFS<ref>[[wikipedia:ReFS |Wikipedia {{---}} ReFS]]</ref>. Реляционные системы управления базами данных, такие как DB2, Informix, Microsoft SQL Server, Oracle Database (начиная с версии 8), Adaptive Server Enterprise и SQLite поддерживают этот тип деревьев для табличных индексов. Среди NoSQL-СУБД, работающих с моделью «ключ—значение», структура данных реализована для доступа к данным в CouchDB, MongoDB (при использовании подсистемы хранения WiredTiger[en]) и Tokyo Cabinet[en].
  
 
== Отличия от B-дерева ==
 
== Отличия от B-дерева ==
 
В B-дереве во всех вершинах хранятся ключи вместе с сопутствующей информацией. В B+-деревом вся информация хранится в листьях, а во внутренних узлах хранятся только копии ключей. Таким образом удается получить максимально возможную степень ветвления во внутренних узлах. Кроме того, листовой узел может включать в себя указатель на следующий листовой узел для ускорения последовательного доступа, что решает одну из главных проблем B-деревьев.
 
В B-дереве во всех вершинах хранятся ключи вместе с сопутствующей информацией. В B+-деревом вся информация хранится в листьях, а во внутренних узлах хранятся только копии ключей. Таким образом удается получить максимально возможную степень ветвления во внутренних узлах. Кроме того, листовой узел может включать в себя указатель на следующий листовой узел для ускорения последовательного доступа, что решает одну из главных проблем B-деревьев.
 +
 +
== Структура дерева ==
 +
 +
== Примeчания ==
 +
<references/>

Версия 03:03, 16 марта 2018

B+-дерево (англ. B+-tree) — структура данных на основе B-дерева, сбалансированное [math]n[/math]-арное дерево поиска с переменным, но зачастую большим количеством потомков в узле. B+‍‍-деревья имеют очень высокий коэффициент ветвления (число указателей из родительского узла на дочерние, обычно порядка 100 или более), что снижает количество операций ввода-вывода, требующих поиска элемента в дереве.

Где используется

Изначально структура предназначалась для эффективного поиска в блочно-ориентированной среде хранения — в частности, для файловых систем. Структура широко применяется в таких файловых системах, как NTFS[1], ReiserFS[2], NSS[3], JFS[4], ReFS[5]. Реляционные системы управления базами данных, такие как DB2, Informix, Microsoft SQL Server, Oracle Database (начиная с версии 8), Adaptive Server Enterprise и SQLite поддерживают этот тип деревьев для табличных индексов. Среди NoSQL-СУБД, работающих с моделью «ключ—значение», структура данных реализована для доступа к данным в CouchDB, MongoDB (при использовании подсистемы хранения WiredTiger[en]) и Tokyo Cabinet[en].

Отличия от B-дерева

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

Структура дерева

Примeчания