В oracle есть b-tree индексы, bitmap-индексы, и еще спецефические (fulltext search помоему, индекс на структурированный xml и может быть еще что-то).
b-tree это сбалансированное дерево высотой обычно не более 5 уровней с логарифмической скоростью доступа. Такой индекс хорош для поиска специфической строки в большой таблице или выборки небольшого объема данных с хорошей селективностью (не слишком много строк в таблице с искомым значением) из таблицы. Область применения - OLTP нагрузки и в DWH тоже полезен.
bitmap-индекс представляет собой таблицу, у которой в заголовках столбцов искомые значения, взятые из индексируемых столбцов индексируемой таблицы, а каждая строка представляет битовую маску: если значение в индексируемой таблице есть, то 1, иначе 0. Каждая строка в битмап-таблице соответсвует одной строке в индексируемой таблице. Такой индекс используется в основном в DWH для поиска по условиям вида (t.col1 = 'A' or t.col2 = 'B') and t.col3 = 'C'. Из такого условия легко собрать битовую маску и пройтись по битмап-индексу.
Можно также заметить, что если бы мы искали по b-tree индексу с условием or нам бы пришлось искать два раза. В то же время, b-tree позволяет искать по условию с неравенством t.col1 > 123 and t.col2 < 234, т.к. дерево отсортировано.
Простой
Средний
