Как в РБД реализованы обычные и составные индексы?

Question

Как реализованы индексы в таких базах данных, как MySQL или Oracle?Я думаю, что обычные индексы хранятся в виде B-деревьев, но не могу найти ничего о составных индексах, которые индексируются по нескольким столбцам.Я ищу названия используемых структур данных, чтобы иметь возможность их изучить.

В более общем плане, где я могу найти дополнительную информацию о деталях реализации базы данных?Я собираюсь пройти курс по этому вопросу гораздо позже в университете, но сейчас мне любопытно.

Answer 1

Составные индексы также используют B-деревья: они просто объединяют индексированные столбцы для определения ключа.В качестве побочного узла Oracle также знает другие типы индексов, т.е.растровые индексы.Но это не зависит от количества проиндексированных столбцов.

Answer 2

B-деревья.Каждый индекс хранится в виде B-дерева, даже составного.

Если вы хотите провести дополнительные исследования того, как организованы индексы, изучите деревья B+ и B*.Для SQL-сервера Книга Калена Делейни «Внутри SQL-сервера»:Механизм хранения — отличная книга об основах SQL Server, включая организацию его индексов.Так что вам обязательно стоит это проверить.

Комментатор отмечает, что Oracle может использовать растровые индексы, которые структурированы совсем иначе, чем B-деревья, но они редко используются для традиционных реляционных баз данных - они чаще используются для приложений типа OLAP и в тех случаях, когда вам нужен быстрый доступ. на неселективной группе данных.

РЕДАКТИРОВАТЬ:SQL Server, например, теперь использует Индексы Columnstore.Если вы выполняете какую-либо работу с большими рабочими нагрузками типа BI, определенно стоит обратить на них внимание, поскольку они хранят ваши данные совершенно иначе, чем B-дерево.

SQL Server теперь также использует другой механизм для таблицы, оптимизированные для памяти Кроме того, это очень полезно для запросов типа OLTP.