Базы данных и индексы B+Trees
Где я могу найти информацию о том, какие базы данных используют B+Trees над B-Trees для реализации своих индексов?
Похоже, что Oracle использует B+Trees. Хотя они не описывают это в своей документации, их графика, похоже, указывает на то, что деревья B + действительно используются.
3 ответа
В Википедии перечислены несколько баз данных, которые поддерживают деревья B+.
Обратите внимание, однако, что для базы данных вполне возможно поддерживать несколько видов индексов
Для SQL Server информация находится здесь: http://msdn.microsoft.com/en-us/library/ms177443.aspx
В SQL Server индексы организованы как B-деревья. Каждая страница в B-дереве индекса называется индексным узлом. Верхний узел B-дерева называется корневым узлом. Нижний уровень узлов в индексе называется листовыми узлами. Любые уровни индекса между корневым и конечным узлами вместе называются промежуточными уровнями. В кластеризованном индексе конечные узлы содержат страницы данных базовой таблицы. Узлы корневого и промежуточного уровня содержат страницы индекса, содержащие строки индекса. Каждая строка индекса содержит значение ключа и указатель либо на страницу промежуточного уровня в B-дереве, либо на строку данных на уровне листа индекса. Страницы на каждом уровне индекса связаны двусвязным списком.
Индекс по умолчанию Oracle - это индекс B*. (Индекс A B* - это "любая" вариация индекса B+.) Oracle упоминает B* в некоторых своих документах DBA и Основах. Вы также можете создавать кластеры, которые используют кластерные индексы. Вы можете создавать растровые индексы в хранилище данных или базе данных OLAP. Растровые индексы работают крайне плохо в базе данных OLTP, хотя они могут работать нормально, если таблица редко обновляется.
Из соображений производительности я уверен, что все базы данных, разработанные для OLTP, используют деревья B* в качестве своих основных индексов. Например, Teradata предназначена для хранилищ данных и использует индексы на основе хешей.