4430
правок
B-дерево (дерево многоканального поиска): различия между версиями
Материал из WEGA
B-дерево (дерево многоканального поиска) (посмотреть исходный код)
Версия от 18:37, 1 марта 2016
, 1 марта 2016→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| (не показаны 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] особенно ценно. | ||
== См. также == | == См. также == | ||
