Какие структуры данных используют индексы в реляционных СУБД?

Как правило, индексы реализованы на основе B-деревьев (чаще B+ Tree). Это сбалансированные поисковые деревья, обеспечивающие быстрый (логарифмический) поиск по ключу и упорядоченное хранение. В некоторых случаях применяются хэш-индексы (для равенства без диапазонов) или битмап-индексы (для столбцов с малым числом различных значений, чаще в аналитических СУБД). Но базовый механизм большинства индексов – B+ Tree, так как он эффективен и для точечного, и для диапазонного поиска.