В.А. Антонюк, А.П. Иванов - Программирование и информатика (Краткий конспект лекций) (1109543), страница 11
Текст из файла (страница 11)
В стандартных библиотеках такой вид контейнераназывается множеством (set), так как для множеств типичными операциями как раз и будут: добавление элемента в множество, удаление элемента из него и определение – входитли элемент в данное множество?Другой класс задач возникает, когда по указанному ключу надо быстро найти связанное сним значение, при этом ключ и значение могут быть произвольного типа, например, ключ– строка, а значение число или наоборот.По своему устройству такой контейнер мало чем отличается от описанного здесь двоичногодерева, просто вместо одного ключа в каждом узле хранится пара «ключ-значение». Нотак как здесь решается задача в немного другой постановке, то программный интерфейс(набор функций) удобно сделать отличающимся от контейнера set.Контейнеры, которые эффективно решают задачу поиска значения, связанного с указанным ключом, называются ассоциативными контейнерами (словарями), так как с каждымключом ассоциируется некоторое значение.
В стандартных библиотеках такие ассоциативные контейнеры представлены контейнерами, называющимися map (от слова «отображение»).Ассоциативный контейнер можно построить на любой из структур данных, описанныхвыше: и на упорядоченном массиве, и на двоичном дереве, и на хэш-таблице, – не следуеттолько забывать о принципиально разной эффективности каждой из структур данных прирешении различных классов задач.B-деревьяВсё, что обсуждалось до сих пор, прекрасно решает различные задачи в программировании, когда весь набор данных помещается в оперативную память компьютера. Если жеданные не могут быть размещены в памяти, возникает необходимость в других способахих организации.Большие файлы с данными (базы данных) могут храниться на жёстком диске компьютеров, которые уже на протяжении многих лет имеют на порядок большую ёмкость по сравнению с оперативной памятью.
К сожалению, диски к тому же имеют ещё и на несколькопорядков меньшее время доступа к данным по сравнению с оперативной памятью – в силу необходимости механического перемещения читающей магнитной головки к нужномуучастку диска.А в таких больших массивах данных тоже бывает нужно добавлять новые данные, удалять избранные данные либо что-то находить — и всё это надо делать с максимальнойэффективностью.52Сейчас появились и быстро дешевеют твердотельные электронные диски, в которых отсутствуют механические части, однако их ёмкость всё ещё существенно уступает ёмкости обычных механических жёстких дисков (а время доступа всё равно гораздо больше времени доступа к данным в оперативной памяти), поэтому алгоритмы, разработанные для решения задачипоиска во «внешней памяти», ещё значительное время будут сохранять актуальность.Давайте попробуем решать те же задачи (поиск, вставка и удаление ключей), которые мырешали с помощью двоичного дерева, для больших данных, хранящихся на стандартномжёстком диске компьютера.Как известно, операционная система предоставляет специальные системные вызовы дляпозиционирования следующей операции чтения на любое нужное смещение от начала файла.
Однако такое позиционирование по меркам времени центрального процессора будеточень долгим, поэтому пытаться применить алгоритм двоичного дерева поиска довольнобессмысленно — он будет чрезвычайно медленным. Стоит также вспомнить и о том, чтожёсткий диск — устройство блочного чтения, позиционирование – операция долгая, нопосле начала чтения быстро считывается и запоминается во временном буфере достаточно большая непрерывная область данных. Происходит так потому, что при чтении самачитающая головка неподвижна, а под ней со скоростью 5-10 тысяч оборотов в секундувращается жёсткий диск.Размер одномоментно считываемой области зависит от настроек файловой системы (которые задаются при форматировании диска средствами операционной системы).
Называетсятакая область кластером или страницей жёсткого диска. Для больших жёстких дисковразмер страницы достигает 64 килобайт и более -– представьте себе, сколько ключей, содержащих целые числа, может поместиться на такой странице! Десятки тысяч.Так как в двоичном дереве поиска основное количество операций производится со смежными узлами, будем такие смежные узлы держать на одной странице:DBFA1C23E45G678Рис.
22: Страничная организация двоичного дереваОбратите внимание, относительно таких страниц мы всё равно видим дерево, но не двоичное, а сильно ветвящееся – на полностью заполненной странице количество дочернихстраниц будет равно количеству узлов на странице плюс одна страница. Ещё одно важноесвойство таких дочерних страниц будет заключаться в том, что ключи в них образуют53непересекающиеся упорядоченные слева направо множества. Очевидно, что для достижения максимальной эффективности все страницы должны быть одинакового размера,соответствующего размеру кластера файловой системы.
Поэтому если какая-то страницазаполнена не полностью, то она всё равно имеет тот же размер, а места отсутствующихключей на такой странице будут вакантными.Теперь вспомним, что операции с данными в уже считанной странице на много порядковбыстрее чтения этой страницы в память. Поэтому держать на ней сбалансированное дерево ключей или что-то подобное – неэффективно, лучше весь доступный размер страницыотвести на хранение полезных данных. То есть, можно «сплющить» двоичное дерево в отсортированный массив ключей (самая компактная структура данных) и параллельный емумассив ссылок на дочерние страницы (размерности на единицу больше, чем размерностьмассива ключей).Заметим, что при таком «сплющивании» каждый ключ данной страницы займёт позициюмежду двумя ссылками на дочерние страницы, левая дочерняя страница будет содержатьключи, меньшие данного ключа, а правая – большие (по-прежнему считаем все ключиуникальными, хотя задача достаточно тривиально обобщается на случай, когда есть неуникальные ключи):A1B2C3D4E5F6G78Рис.
23: Страничная организация двоичного дереваЗдесь вместо ссылок будут фигурировать смещения начала каждой дочерней страницыот начала файла – это смещение надо указать системному вызову операционной системыдля перемещения позиции следующего чтения к началу нужной страницы. Помним такжео том, что в силу того, что массив ключей страницы отсортирован, в нём можно быстроискать дихотомией (делением массива пополам).Так как получаемые страницы достаточно велики (дерево страниц сильно ветвится), то мысможем буквально за пару-тройку перемещений позиции чтения находить данные в базеданных, хранящей многие миллиарды ключей.Разберёмся, как такое дерево страниц построить – как в него добавлять ключи? Вставкановых страниц «как в двоичном дереве» тут невозможна – будет очень неэффективно«раздвигать» файл на жёстком диске, как мы это делали с массивом в оперативной памяти.Вместо этого все новые страницы будут добавляться просто в конец файла, с указаниемправильного смещения к ней в нужном месте родительской страницы.
Но в этих операцияхдобавления новой страницы тоже можно сильно сэкономить, если на каждой страницепредусмотреть достаточное количество вакантных мест под ключи. Ну, и сами страницыдолжны образовывать каким-то образом сбалансированное сильно ветвящееся дерево –чтобы избежать длинных цепочек страниц в каком-нибудь неудачном случае.Именно такой алгоритм и разработали Бэйер и Маккрейт (Bayer, McCreight) в 1970 го54ду, в честь одного из них структура данных получила название -дерево ( -дерево – небинарное!).Определение. -деревом называется сильно ветвящееся дерево страниц, в котором каждая страница, кроме, быть может, корневой, содержит не менее и не более 2 ключей. Число называется порядком -дерева.Довольно очевиден алгоритм поиска в таком дереве: начинаем с корневой страницы (которую для простоты можно просто всю целиком держать в памяти), находим между какойпарой ключей расположено значение искомого ключа и проходим к дочерней странице посвязи, лежащей между этими двумя ключами.
Если искомое значение меньше минимального ключа страницы или больше максимального, то проходим по самой левой или самойправой связи соответственно. В случае сбалансированного дерева очевидно, что такой поиск займет (log ) операций.Рассмотрим алгоритм вставки нового ключа с одновременной балансировкой дерева страниц:A)...12475Б)86......78...1237485 6......3В)...12 345 6......Рис. 24: Вставка в B-дерево1. Мы дошли до листовой страницы и не нашли искомого ключа.2. Если на странице меньше 2 ключей (она не заполнена) – то просто вставляем ключв в нужное место отсортированного массива ключей этой страницы.
Все дочерниесвязи у листовой страницы – нулевые.3. Если вставлять некуда (рис.24 А: страница заполнена, на ней уже есть 2 ключейплюс один ключ, который мы хотим вставить, всего – 2 + 1 ключей), то всё равновставляем этот ключ в отсортированный массив (рис.24 Б: массив уже в памяти!),но сразу после этого – делим его пополам: первых по порядку ключей оставляемна текущей странице, для последних по порядку ключей создаем новую листовуюстраницу (и записываем её в конец файла), а один средний ключ – отправляем вродительскую страницу.4. Если на родительской странице есть вакансия – вставляем «лишний» ключ в нужноеместо и образуем справа от него новую связь на новую листовую страницу (рис.24В).555.
Если вакансии на родительской странице нет – повторяем для неё п.3.6. Если дошли до корня, в котором нет вакансии – по алгоритму п.3 образуем новыйкорень ровно с одним ключом в нём (определение -дерева делает специальную оговорку для корня).Получается, что -дерево растёт от листьев к корню, – в отличие от бинарного дерева,где рост происходит в листьях. В самом худшем случае мы поднимемся до корня, то естьпройдём всю высоту дерева, поэтому оценка производительности вставки элемента будеттакой же, как и для времени поиска: (log ).Алгоритм удаления ключа – просто обратный к алгоритму вставки: вместо разбиения страниц, при необходимости, происходит их слияние с заимствованием одного элемента из родительской страницы и с уничтожением ставшей ненужной одной связи в родительскойстранице.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
