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

Question

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

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

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

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

table customer:
id    number
name   varchar
phone_number   varchar
city   varchar

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

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

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

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

Answer 1

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

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

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

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

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

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

Answer 2

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

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

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

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

Answer 3

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

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

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

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

Answer 4

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

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

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

Answer 5

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

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

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

Answer 6

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

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