Как создаются индексы
Вы, читатель, возможно, уже изучали курс структур данных и осведомлены о том, что хеш-таблицы (hash tables) — это весьма многообещающее средство создания индексов. В ранних СУБД хеш-таблицы использовались особенно интенсивно. Но сегодня наиболее распространенной структурой данных, применяемой для создания индексов, является В-дерево (B-tree; буква В служит сокращением термина «balanced» — сбалансированное). Структура В-дерева представляет собой обобщение так называемого сбалансированного бинарного дерева поиска (balanced binary search tree): если вершина бинарного дерева обладает, самое большее, двумя дочерними вершинами, вершина В-дерева может иметь произвольное число дочерних вершин. Если принять во внимание, что данные В-дерева обычно размещаются на диске, а не в оперативной памяти, структура проектируется таким образом, чтобы информация о каждой ее вершине занимала отдельный блок диска. Поскольку обычный размер блока достигает 212 (4096) байт, в одном блоке вполне возможно хранить данные о сотнях дочерних вершин дерева. Таким образом, при поиске данных по В-дереву необходимость обращения к более чем нескольким блокам возникает сравнительно редко.
Трудоемкость дисковых операций пропорциональна количеству запрашиваемых блоков диска. Поэтому поиск по В-дереву, затрагивающий, как правило, всего несколько блоков диска, существенно более эффективен, нежели бинарный поиск, в процессе выполнения которого приходится посещать вершины дерева, относящиеся к многим различным блокам. Указанное различие между деревьями бинарного поиска и В-деревьями — это один из характерных примеров того, что структуры данных, наиболее подходящие для хранения данных в оперативной памяти, не обязательно столь же эффективны, если данные располагаются на диске.
Буду печатать курсовой проект, и поэтому Очень скоро понадобиться широкоформатная печать на ватмане. Конечно это не такое дорого удовольствие, но всё же проблематично.
