Внутренняя структура индексов
СУБД ЛИНТЕР использует для индексов B*-деревья,
сбалансированные таким образом, чтобы время доступа к любой записи было одинаковым.
Верхние блоки (блоки ветвей) B*-дерева индекса содержат данные индекса,
указывающие на блоки индекса более низкого уровня. Блоки индекса низшего
уровня (блоки листьев) содержат каждое индексированное значение данных и
соответствующий ROWID (системный номер записи), используемый
для нахождения записи;
блоки листьев связаны в двусвязный список. Индексы по столбцам, содержащим
символьные данные, базируются на двоичных значениях символов в наборе символов БД.
Для уникального индекса на каждое значение данных существует один ROWID.
Для неуникального индекса ROWID включен в ключ. Неуникальные индексы
отсортированы по ключу и по ROWID. Значения ключей, состоящие только из пустых
значений, не индексируются. Для уникального индекса две строки
не могут состоять из одних пустых значений.
Структура B*-дерева имеет следующие преимущества:
-
все блоки листьев в дереве имеют одинаковую глубину, так что извлечение любой записи из любого места индекса требует приблизительно одинакового времени;
-
B*-деревья индексов автоматически балансируются;
-
все блоки в B*-дереве в среднем заполнены на 3/4;
-
B*-деревья обеспечивают высокую скорость извлечения данных для широкого спектра запросов, включая поиск по точному совпадению и по диапазону значений;
-
вставки, обновления и удаления эффективны и поддерживают порядок ключей для быстрого извлечения;
-
производительность B*-деревьев не падает с ростом размера таблиц.