Как выглядит индекс B-дерева более чем на 1 столбец?

Итак, я читал об индексах и их реализации, и я наткнулся на этот сайт, который содержит краткое объяснение индексов b-tree:

http://20bits.com/articles/interview-questions-database-indexes/

Индекс b-дерева имеет смысл для индексов, которые находятся только в одном столбце, но пусть я создаю индекс с несколькими столбцами, как тогда работает b-дерево? Какова ценность каждого node в b-дереве?

Например, если у меня есть эта таблица:

table customer:
id    number
name   varchar
phone_number   varchar
city   varchar

и я создаю индекс на: (id, name, city)

а затем выполните следующий запрос:

SELECT id, name 
  FROM customer
 WHERE city = 'My City';

как этот запрос использует индекс с несколькими столбцами или не использует его, если индекс не создан как (город, идентификатор, имя) или (город, имя, идентификатор) вместо?

Ответ 1

Представьте, что ключ представлен кортежем Python (col1, col2, col3)... операция индексирования включает в себя сравнение tuple_a с tuple_b..., если вы не знаете, какое значение col1 и col2, который вам интересен, но только col3, тогда он должен будет прочитать весь индекс ( "полное сканирование индекса" ), что не так эффективно.

Если у вас есть индекс (col1, col2, col3), вы можете ожидать, что любая RDBMS будет использовать индекс (прямо), когда предложение WHERE содержит ссылку на (1) все 3 столбца (2) оба col1 и col2 (3) только col1.

В противном случае (например, только col3 в предложении WHERE) либо RDBMS вообще не будет использовать этот индекс (например, SQLite), либо выполнит полное сканирование индекса (например, Oracle) [если другой индекс лучше].

В вашем конкретном примере, предполагая, что идентификатор является уникальным идентификатором клиента, бессмысленно указывать его в индексе (кроме индекса, который ваша СУБД должна настроить для первичного ключа или столбца, отмеченного как UNIQUE).

Ответ 2

В большинстве реализаций ключ представляет собой просто более длинный ключ, который включает все значения ключа, с разделителем. Нет волшебства, -)

В вашем примере значения ключа могут выглядеть примерно как

"123499|John Doe|Conway, NH"
"32144|Bill Gates| Seattle, WA"

Одна из характеристик этих индексов с составными ключами заключается в том, что промежуточные узлы дерева могут использоваться в некоторых случаях для "покрытия" запроса.

Например, если запрос заключается в том, чтобы найти имя и город с идентификатором, поскольку идентификатор является первым в индексе, индекс может эффективно выполнять поиск. Однажды в промежуточном node он может "анализировать" имя и город, от ключа, и не нужно идти в лист node, чтобы читать то же самое.

Если, однако, запрос хотел также отобразить номер телефона, тогда логика будет следовать за листом, когда будет найдена полная запись.

Ответ 3

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

Быстрое сканирование полного индекса, в котором многоблочные чтения используются для перемещения по всему сегменту индекса.
Полное сканирование индекса, в котором индекс читается в логическом порядке блоков (я считаю, что прочитал, что в последних версиях Oracle может использовать для этого многоблочные чтения, но на самом деле вам следует рассчитывать на одноблочные чтения)
Сканирование inddex skip, при котором очень низкая мощность для неосновных ведущих столбцов позволяет Oracle выполнять несколько сканирований диапазона индексов, по одному для каждого уникального значения ведущего столбца. Это довольно редко в моем опыте.

Ищите статьи Ричарда Фута или Джонатана Льюиса для получения дополнительной информации о внутренних компонентах Oracle.

Ответ 4

Некоторые реализации просто объединяют значения в порядке столбцов с разделителями.

Другим решением является простое b-дерево внутри b-дерева. Когда вы попадаете в лист в первом столбце, вы получаете как список совпадающих записей, так и мини-b-дерево следующего столбца и т.д. Таким образом, порядок столбцов, указанных в индексе, имеет огромное значение для того, будет ли этот индекс полезен для определенных запросов.

Вот связанный с этим вопрос, который я написал на прошлой неделе:

Сбрасывается ли SQL Server при использовании составного кластерного индекса?

Ответ 5

Помимо описанного выше механизма "составного ключа", одна из возможностей - это kdtree, которая работает как двоичное дерево, но по мере прохождения каждого уровня вы проходите через измерения k. То есть первый уровень дерева разделяет первое измерение на две части, второй уровень разделяет второе измерение, уровень k+1 th снова разделяет первое измерение и т.д. Это позволяет эффективно разбивать данные на любое число размеров. Этот подход распространен в "пространственных" базах данных (например, Oracle Spatial, PostGIS и т.д.), Но, вероятно, не так полезен в "обычных" многоиндексных таблицах.

http://en.wikipedia.org/wiki/Kd-tree

Ответ 6

Он может использовать индекс (id, name, city) для удовлетворения предиката City =?, но очень неэффективно.

Чтобы использовать индекс для удовлетворения этого запроса, ему нужно будет пройти большую часть древовидной структуры, ища записи с нужным городом. Это, вероятно, порядок magnatude быстрее, чем сканирование таблицы!

Индекс (city, name, id) будет лучшим индексом для вашего запроса. Он легко найдет все требуемые записи города и не будет нуждаться в доступе к базовой таблице, чтобы получить значения id и name.