Как реализованы индексы в таких базах данных, как MySQL или Oracle? Я думаю, что обычные индексы хранятся в виде B-деревьев, но ничего не могу найти о составных индексах, индексирующих несколько столбцов. Я ищу названия используемых структур данных, чтобы исследовать их.
В более общем смысле, где я могу найти дополнительную информацию о деталях реализации базы данных? Я собираюсь пройти этот курс намного позже в университете, но сейчас мне любопытно.
Составные индексы также используют B-деревья, они просто объединяют проиндексированные столбцы для определения ключа. В качестве побочного узла Oracle также знает другие типы индексов, то есть битовые индексы. Но это не зависит от количества проиндексированных столбцов.
B-деревья. Каждый индекс хранится в виде B-дерева, даже составной.
Если вы хотите больше узнать об организации индексов, изучите деревья B+ и деревья B*. Для SQL Server: Kalen Delaney Inside SQL Server: The Storage Engine — отличная книга об основах SQL Server, в том числе об организации его индексов. Так что вам обязательно стоит это проверить.
Комментатор указывает, что Oracle может использовать битовые индексы, которые структурированы совсем иначе, чем B-деревья, но они редко используются для традиционных реляционных баз данных — они используются чаще для приложений типа OLAP и в случаях, когда вам нужен быстрый доступ. на неселективной группе данных.
РЕДАКТИРОВАТЬ: SQL Server, например, теперь использует индексы Columnstore. Если вы работаете с большими рабочими нагрузками типа BI, определенно стоит обратить внимание на них, поскольку они хранят ваши данные совершенно иначе, чем B-Tree.
SQL Server теперь также использует другой механизм для таблиц, оптимизированных для памяти. , и это очень полезно для запросов типа OLTP.
