B-дерево (дерево многоканального поиска): различия между версиями

Перейти к навигации Перейти к поиску
м
 
(не показаны 3 промежуточные версии этого же участника)
Строка 4: Строка 4:


Задача связана с хранением линейно упорядоченного множества элементов таким образом, чтобы операции FIND, INSERT и DELETE для типа данных DICTIONARY могли эффективно исполняться.
Задача связана с хранением линейно упорядоченного множества элементов таким образом, чтобы операции FIND, INSERT и DELETE для типа данных DICTIONARY могли эффективно исполняться.
В 1972 году Байером и Маккрейтом был введен класс B-деревьев как одного из способов реализации «индекса динамически меняющегося файла с произвольным доступом» [6, стр. 173]. С тех пор B-деревья получили широкое распространение в контексте работы с базами данных и в сообществе разработчиков алгоритмов; одним из свидетельств их быстрого и широкого принятия может служить тот факт, что авторитетный обзор B-деревьев за авторством Комера [9] появился уже в 1979 году и описывал структуру данных B-дерева как «вездесущую».
В 1972 году Байером и Маккрейтом был введен класс [[B-Дерево|B-деревьев]] как одного из способов реализации «индекса динамически меняющегося файла с произвольным доступом» [6, стр. 173]. С тех пор B-деревья получили широкое распространение в контексте работы с базами данных и в сообществе разработчиков алгоритмов; одним из свидетельств их быстрого и широкого принятия может служить тот факт, что авторитетный обзор B-деревьев за авторством Комера [9] появился уже в 1979 году и описывал структуру данных B-дерева как «вездесущую».


== Нотация ==
== Нотация ==
Строка 140: Строка 140:




'''Ссылка на код'''
'''Ссылки на код'''




Существует множество коммерческих и бесплатных реализаций B-деревьев и (a, b)-деревьев, доступных для скачивания. В их число входят реализации на базе C++, являющиеся компонентами библиотеки LEDA (http://www. algorithmic-solutions.com), библиотеки STXXL (http:// stxxl.sourceforge.net) и библиотеки TPIE (http://www. cs.duke.edu/TPIE), а также реализации на базе Java, являющиеся компонентами библиотеки javaxxl (http://www. xxl-library.de). Кроме того, реализации на псевдокоде можно найти почти в любом учебнике по системам баз данных или алгоритмам и структурам данных – например, в [10, 11]. Поскольку учебники почти всегда оставляют детали реализации операции DELETE в качестве упражнения для читателя, обсуждение в работе Яннинка [15] особенно ценно.
Существует множество коммерческих и бесплатных реализаций B-деревьев и (a, b)-деревьев, доступных для скачивания. В их число входят реализации на базе C++, являющиеся компонентами библиотеки LEDA ([http://www.algorithmic-solutions.com]), библиотеки STXXL ([http://stxxl.sourceforge.net]) и библиотеки TPIE ([http://www.cs.duke.edu/TPIE]), а также реализации на базе Java, являющиеся компонентами библиотеки javaxxl ([http://www.xxl-library.de]). Кроме того, реализации на псевдокоде можно найти почти в любом учебнике по системам баз данных или алгоритмам и структурам данных – например, в [10, 11]. Поскольку учебники почти всегда оставляют детали реализации операции DELETE в качестве упражнения для читателя, обсуждение в работе Яннинка [15] особенно ценно.


== См. также ==
== См. также ==
4492

правки

Навигация