Многоуровневые индексы
При поиске по индексу тем не менее производится чтение записей файла данных. Если файл данных достаточно большой либо сами записи имеют размер, значительно меньший размера стандартного логического блока диска в операционной системе, то объем считываемых данных при операциях поиска значительно превышает объем данных, содержащихся в записи. Исключить это можно, если в индекс помещать не только ссылку на запись, но и значение индексируемого поля.
Тогда при поиске можно обойтись только индексной таблицей. Однако этот вариант ведет к значительному увеличению размера индекса. Компромиссный вариант заключается в построении "индекса для индекса", содержащего ссылки на записи индексной таблицы и значения индексируемого поля для этих записей. Такой индекс называется двухуровневым. Соответственно поиск в нем состоит из двоичного поиска в индексе верхнего уровня, во время которого определяется интервал индекса нижнего уровня. В этом интервале и завершается поиск.
Многоуровневое индексирование эффективно также при большой размерности индексной таблицы, когда она полностью не размещается в памяти.
