Внутренняя структура индексов

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

Для уникального индекса на каждое значение данных существует один ROWID. Для неуникального индекса ROWID включен в ключ. Неуникальные индексы отсортированы по ключу и по ROWID. Значения ключей, состоящие только из пустых значений, не индексируются. Для уникального индекса две строки не могут состоять из одних пустых значений.

Структура B*-дерева имеет следующие преимущества:

  • все блоки листьев в дереве имеют одинаковую глубину, так что извлечение любой записи из любого места индекса требует приблизительно одинакового времени;

  • B*-деревья индексов автоматически балансируются;

  • все блоки в B*-дереве в среднем заполнены на 3/4;

  • B*-деревья обеспечивают высокую скорость извлечения данных для широкого спектра запросов, включая поиск по точному совпадению и по диапазону значений;

  • вставки, обновления и удаления эффективны и поддерживают порядок ключей для быстрого извлечения;

  • производительность B*-деревьев не падает с ростом размера таблиц.