Существует множество способов организации индексов:
- В плотных индексах для каждого значения ключа имеется отдельная запись индекса, указывающая место размещения конкретной записи. Неплотные (разреженные) индексы строятся в предположении, что на каждой странице памяти хранятся записи, отсортированные по значениям индексируемого атрибута. Тогда для каждой страницы в индексе задаётся диапазон значений ключей хранимых в ней записей, и поиск записи осуществляется среди записей на указанной странице.
- Для больших индексов актуальна проблема сжатия ключа. Наиболее распространенный метод сжатия основан на устранении избыточности хранимых данных. Последовательно идущие значения ключа обычно имеют одинаковые начальные части, поэтому в каждой записи индекса можно хранить не полное значение ключа, а лишь информацию, позволяющую восстановить его из известного предыдущего значения. Такой индекс называется сжатым.
- Одноуровневый индекс представляет собой линейную совокупность значений одного или нескольких полей записи. На практике он используется редко. В развитых СУБД применяются более сложные методы организации индексов. Особенно эффективными являются многоуровневые индексы в виде сбалансированных деревьев (B-деревьев, balance trees).