Базы данных и индексы B + Trees

Question

Где я могу найти информацию о том, какие базы данных используют B + Trees над B-Trees для реализации своих индексов?

Похоже, что Oracle использует деревья B +. Хотя они не описывают это в своей документации, их графика указывает на то, что деревья B + действительно используются.

Answer 1

Википедия перечисляет количество баз данных , которые поддерживают деревья B +.

Обратите внимание, однако, что для базы данных вполне возможно поддерживать несколько видов индексов

Answer 2

Индекс по умолчанию Oracle - это индекс B *. (Индекс B * - это «любая» вариация индекса B +.) Oracle упоминает B * в некоторых своих документах DBA и Основах. Вы также можете создавать кластеры, которые используют кластерные индексы. Вы можете создавать растровые индексы в хранилище данных или в базе данных OLAP. Растровые индексы очень плохо работают в базе данных OLTP, хотя они могут работать нормально, если таблица редко обновляется.

По соображениям производительности я уверен, что все базы данных, разработанные для OLTP, используют деревья B * в качестве своих основных индексов. Например, Teradata предназначена для хранилищ данных и использует индексы на основе хешей.

Answer 3

Для SQL Server информация здесь: http://msdn.microsoft.com/en-us/library/ms177443.aspx

В SQL Server индексы организованы как B-деревья. Каждая страница в B-дереве индекса называется индексным узлом. Верхний узел B-дерева называется корневым узлом. Нижний уровень узлов в индексе называется листовыми узлами. Любые уровни индекса между корневым и конечным узлами вместе называются промежуточными уровнями. В кластеризованном индексе конечные узлы содержат страницы данных базовой таблицы. Узлы корневого и промежуточного уровня содержат страницы индекса, содержащие строки индекса. Каждая строка индекса содержит значение ключа и указатель либо на страницу промежуточного уровня в B-дереве, либо на строку данных на уровне листа индекса. Страницы на каждом уровне индекса связаны двусвязным списком.