B⁺-дерево

B⁺-дерево — структура данных на основе B-дерева, сбалансированное -арное дерево поиска с переменным, но зачастую большим количеством потомков в узле. B⁺-дерево состоит из корня, внутренних узлов и листьев, корень может быть либо листом, либо узлом с двумя и более потомками. Изначально структура предназначалась для хранения данных в целях эффективного поиска в блочно-ориентированной среде хранения — в частности, для файловых систем; применение связано с тем, что в отличие от бинарных деревьев поиска, B⁺-деревья имеют очень высокий коэффициент ветвления (число указателей из родительского узла на дочерние — обычно порядка 100 или более), что снижает количество операций ввода-вывода, требующих поиска элемента в дереве. Вариант B⁺-дерева, в котором все значения сохранялись в листовых узлах, систематически рассмотрен в 1979 году, притом отмечено, что такие структуры использовались IBM в технологии файлового доступа для мейнфреймов по крайней мере с 1973 года. Структура широко применяется в файловых системах — 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) и .