Как регулярные и составные индексы реализуются в RDB?

Question

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

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

Answer 1

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

Answer 2

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

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

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

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

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