Индексы | Tarantool
Документация на русском языке
поддерживается сообществом

Индексы

Индекс — это специальная структура данных, которая хранит группу ключевых значений и указателей. Индекс используется для эффективного управления данными.

Как и для спейсов, для индексов следует указать имена, а Tarantool определит уникальный числовой идентификатор («ID индекса»).

У индекса всегда есть определенный тип. Тип индекса по умолчанию — TREE. TREE-индексы поддерживаются обоими движками Tarantool, могут индексировать уникальные и неуникальные значения, поддерживают поиск по компонентам ключа, сравнение ключей и упорядочивание результатов. Движок memtx поддерживает и другие типы индексов: HASH, RTREE и BITSET.

Индекс может быть многокомпонентным, то есть можно объявить, что ключ индекса состоит из двух или более полей в кортеже в любом порядке. Например, для обычного TREE-индекса максимальное количество частей равно 255.

Индекс может быть уникальным, то есть можно объявить, что недопустимо дважды задавать одно значение ключа.

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

На индексы распространяются определенные ограничения. Более подробную информацию см. на странице Ограничения.

Можно создать генератор индексов, используя последовательность (sequence). Чтобы узнать подробности, обратитесь к практическому руководству.

Типы полей не следует путать с типами индексов как структур данных. О типах индексов можно прочитать ниже.

Индексы ограничивают значения, которые Tarantool может хранить в формате MsgPack. Вот почему, например, есть отдельные типы полей 'unsigned' (число без знака) и 'integer' (целое число), хотя в MsgPack они оба хранятся как целочисленные значения. Индекс типа 'unsigned' содержит только неотрицательные целочисленные значения, а индекс типа 'integer' содержит любые целочисленные значения.

По умолчанию тип поля — 'unsigned', тип индекса — TREE. Хотя в качестве типа индексированого поля 'nil' использовать нельзя, индексы могут содержать nil как опцию, которая не используется по умолчанию.

Подробную информацию см. на странице Описание типов полей, а также в более развернутом Описании типов индексированных полей в справочнике.

Имя типа поля Field type Тип индекса
'boolean' boolean boolean
'integer' (may also be called 'int') integer, может включать в себя значения unsigned (без знака) TREE или HASH
'unsigned' (без знака, также может называться 'uint' или 'num', но 'num' объявлен устаревшим) unsigned TREE, BITSET или HASH
'double' double TREE или HASH
'number' number, может включать в себя значения типа integer, double или decimal TREE или HASH
'decimal' decimal TREE или HASH
'string' (строка, также может называться 'str') string TREE, BITSET или HASH
'varbinary' varbinary TREE, HASH или BITSET (с версии 2.7)
'uuid' uuid TREE или HASH
datetime datetime TREE
'array' array RTREE
'scalar' may include nil, boolean, integer, unsigned, number, decimal, string, varbinary, or uuid values |
When a scalar field contains values of different underlying types, the key order is: nils, then booleans, then numbers, then strings, then varbinaries, then uuids.
TREE или HASH

Индекс всегда относится к определенному типу. Для разных сценариев использования требуются разные типы индексов.

Обзор характеристик индексов приведен в следующей таблице:

Характеристика TREE HASH RTREE BITSET
уникальный + + - -
неуникальный + - + +
is_nullable + - - -
может быть составным (multi-part) + + - -
индекс по массиву (multikey) + - - -
поиск по части ключа + - - -
может быть по первичному ключу + + - -
exclude_null (версии 2.8+) + - - -
типы итераторов ALL, EQ, REQ, GT, GE, LT, LE ALL, EQ, GT ALL, EQ, GT, GE, LT, LE, OVERLAPS, NEIGHBOR ALL, EQ, BITS_ALL_SET, BITS_ANY_SET, BITS_ALL_NOT_SET

Тип индекса по умолчанию — „TREE“. Движки memtx и vinyl предоставляют TREE-индексы, которые могут индексировать уникальные и неуникальные значения, поддерживают поиск по компонентам ключа, сравнение ключей и упорядоченные результаты.

Это универсальный тип индексов, в большинстве случаев он подойдет лучше всего.

Кроме того, движок memtx поддерживает следующие типы индексов: HASH, RTREE и BITSET.

HASH-индексы требуют уникальности полей и почти во всех отношениях проигрывают индексам типа TREE. Поэтому мы не рекомендуем использовать их в приложениях. В настоящее время Tarantool поддерживает HASH в основном для обратной совместимости.

Вот несколько советов. Не используйте HASH-индекс:

  • если просто хочется
  • если вы думаете, что HASH быстрее, без измерения производительности
  • если вы хотите выполнять перебор данных
  • по первичному ключу
  • как единственный индекс

Используйте HASH-индекс:

  • если это вторичный ключ
  • если вы на сто процентов уверены, что его не придется делать неуникальным
  • если вы обнаружили значимое увеличение производительности в ходе проведенных измерений
  • если вы экономите каждый байт на кортежах (HASH немного компактнее)

RTREE — это многомерный индекс, который поддерживает до 20 измерений. Он используется, в частности, для индексирования пространственной информации, такой как географические объекты. В этом примере мы показываем, как использовать пространственный поиск с помощью RTREE-индекса.

RTREE-индекс не может быть первичным и не может быть уникальным. Индекс такого типа может содержать параметры измерения и расстояния — dimension и distance соответственно. Определение parts должно включать только один компонент типа array. RTREE-индекс может принимать два типа функции расстояния distance: euclid, то есть Евклидова метрика, или manhattan, то есть расстояние городских кварталов.

Пример 1:

my_space = box.schema.create_space("tester")
my_space:format({ { type = 'number', name = 'id' }, { type = 'array', name = 'content' } })
hash_index = my_space:create_index('primary', { type = 'tree', parts = {'id'} })
rtree_index = my_space:create_index('spatial', { type = 'RTREE', unique = false, parts = {'content'} })

Таким образом, соответствующее поле кортежа может быть массивом типа array из 2 или 4 чисел. 2 числа обозначают точку {x, y}; 4 числа обозначают прямоугольник {x1, y1, x2, y2}, где (x1, y1) и (x2, y2) — диагональные точки прямоугольника.

my_space:insert{1, {1, 1}}
my_space:insert{2, {2, 2, 3, 3}}

Результаты выборки зависят от выбранного итератора. Итератор EQ, который используется по умолчанию, ищет точный прямоугольник, точка рассматривается как прямоугольник нулевой ширины и высоты:

tarantool> rtree_index:select{1, 1}
---
- - [1, [1, 1]]
...

tarantool> rtree_index:select{1, 1, 1, 1}
---
- - [1, [1, 1]]
...

tarantool> rtree_index:select{2, 2}
---
- []
...

tarantool> rtree_index:select{2, 2, 3, 3}
---
- - [2, [2, 2, 3, 3]]
...

Итератор ALL, который используется по умолчанию, если не указан ключ, выбирает все кортежи в произвольном порядке:

tarantool> rtree_index:select{}
---
- - [1, [1, 1]]
  - [2, [2, 2, 3, 3]]
...

Итератор LE (меньше или равно) ищет кортежи с прямоугольниками, которые находятся в пределах заданного прямоугольника:

tarantool> rtree_index:select({1, 1, 2, 2}, {iterator='le'})
---
- - [1, [1, 1]]
...

Итератор LT (меньше или строго меньше) ищет кортежи с прямоугольниками, которые находятся строго в пределах заданного прямоугольника:

tarantool> rtree_index:select({0, 0, 3, 3}, {iterator = 'lt'})
---
- - [1, [1, 1]]
...

Итератор GE ищет кортежи с прямоугольниками, в пределах которых находится заданный прямоугольник:

tarantool> rtree_index:select({1, 1}, {iterator = 'ge'})
---
- - [1, [1, 1]]
...

Итератор GT ищет кортежи с прямоугольниками, строго в пределах которых находится заданный прямоугольник:

tarantool> rtree_index:select({2.1, 2.1, 2.9, 2.9}, {iterator = 'gt'})
---
- []
...

Итератор OVERLAPS ищет кортежи с прямоугольниками, перекрывающими указанный прямоугольник:

tarantool> rtree_index:select({0, 0, 10, 2}, {iterator='overlaps'})
---
- - [1, [1, 1]]
  - [2, [2, 2, 3, 3]]
...

Итератор NEIGHBOR ищет все кортежи и упорядочивает их по расстоянию до заданной точки:

tarantool> for i=1,10 do
         >    for j=1,10 do
         >        my_space:insert{i*10+j, {i, j, i+1, j+1}}
         >    end
         > end
---
...

tarantool> rtree_index:select({1, 1}, {iterator = 'neighbor', limit = 5})
---
- - [11, [1, 1, 2, 2]]
  - [12, [1, 2, 2, 3]]
  - [21, [2, 1, 3, 2]]
  - [22, [2, 2, 3, 3]]
  - [31, [3, 1, 4, 2]]
...

Пример 2:

3-мерные, 4-мерные или многомерные RTREE индексы используются так же, как и для двумерные, только пользователь должен указать больше координат в запросах. Вот небольшой пример использования для 4-мерного дерева:

tarantool> my_space = box.schema.create_space("tester")
tarantool> my_space:format{ { type = 'number', name = 'id' }, { type = 'array', name = 'content' } }
tarantool> primary_index = my_space:create_index('primary', { type = 'TREE', parts = {'id'} })
tarantool> rtree_index = my_space:create_index('spatial', { type = 'RTREE', unique = false, dimension = 4, parts = {'content'} })
tarantool> my_space:insert{1, {1, 2, 3, 4}} -- вставка 4D-точки
tarantool> my_space:insert{2, {1, 1, 1, 1, 2, 2, 2, 2}} -- вставка 4D-тела

tarantool> rtree_index:select{1, 2, 3, 4} -- поиск определенной точки
---
- - [1, [1, 2, 3, 4]]
...

tarantool> rtree_index:select({0, 0, 0, 0, 3, 3, 3, 3}, {iterator = 'LE'}) -- выборка из 4D-тела
---
- - [2, [1, 1, 1, 1, 2, 2, 2, 2]]
...

tarantool> rtree_index:select({0, 0, 0, 0}, {iterator = 'neighbor'}) -- выборка соседей
---
- - [2, [1, 1, 1, 1, 2, 2, 2, 2]]
  - [1, [1, 2, 3, 4]]
...

Примечание

Не рекомендуется использовать с операцией select итератор NEIGHBOR без указанного значения limit. В этом случае будет получен спейс целиком, упорядоченный по возрастанию расстояния. Это может отразиться на производительности, поскольку в спейсе может храниться огромное количество данных.

Другая типичная ошибка — указать тип итератора без кавычек следующим образом: rtree_index:select(rect, {iterator = LE}). В этом случае LE представляет собой неопределенную переменную и обрабатывается как nil, поэтому итератор считается незаданным, и будет использован итератор по умолчанию EQ.

Bitset — это битовая маска. BITSET следует использовать для поиска по битовым маскам. Это может быть, например, сохранение вектора атрибутов и поиск по этим атрибутам.

Пример 1:

Скрипт ниже показывает создание и поиск с помощью индекса BITSET. Обратите внимание, что BITSET не может быть уникальным, поэтому сначала создается индекс по первичному ключу, а битовые значения вводятся в шестнадцатеричном виде для удобства чтения.

tarantool> my_space = box.schema.space.create('space_with_bitset')
tarantool> my_space:create_index('primary_index', {
         >   parts = {1, 'string'},
         >   unique = true,
         >   type = 'TREE'
         > })
tarantool> my_space:create_index('bitset_index', {
         >   parts = {2, 'unsigned'},
         >   unique = false,
         >   type = 'BITSET'
         > })
tarantool> my_space:insert{'Tuple with bit value = 01', 0x01}
tarantool> my_space:insert{'Tuple with bit value = 10', 0x02}
tarantool> my_space:insert{'Tuple with bit value = 11', 0x03}
tarantool> my_space.index.bitset_index:select(0x02, {
         >   iterator = box.index.EQ
         > })
---
- - ['Tuple with bit value = 10', 2]
...
tarantool> my_space.index.bitset_index:select(0x02, {
         >   iterator = box.index.BITS_ANY_SET
         > })
---
- - ['Tuple with bit value = 10', 2]
  - ['Tuple with bit value = 11', 3]
...
tarantool> my_space.index.bitset_index:select(0x02, {
         >   iterator = box.index.BITS_ALL_SET
         > })
---
- - ['Tuple with bit value = 10', 2]
  - ['Tuple with bit value = 11', 3]
...
tarantool> my_space.index.bitset_index:select(0x02, {
         >   iterator = box.index.BITS_ALL_NOT_SET
         > })
---
- - ['Tuple with bit value = 01', 1]
...

Пример 2:

tarantool> box.schema.space.create('bitset_example')
tarantool> box.space.bitset_example:create_index('primary')
tarantool> box.space.bitset_example:create_index('bitset',{unique = false, type = 'BITSET', parts = {2,'unsigned'}})
tarantool> box.space.bitset_example:insert{1,1}
tarantool> box.space.bitset_example:insert{2,4}
tarantool> box.space.bitset_example:insert{3,7}
tarantool> box.space.bitset_example:insert{4,3}
tarantool> box.space.bitset_example.index.bitset:select(2, {iterator = 'BITS_ANY_SET'})

Получим следующий результат:

---
- - [3, 7]
  - [4, 3]
...

поскольку (7 AND 2) не равно 0, и (3 AND 2) не равно 0.

Кроме того, есть операции с итераторами с индексом. Их можно использовать только с кодом на языках Lua и C/C++. Итераторы с индексом предназначены для обхода индексов по одному ключу за раз, поскольку используют особенности каждого типа индекса. Например, их можно использовать для оценки логических выражений при обходе BITSET-индексов или при обходе TREE-индексов в порядке по убыванию.

Нашли ответ на свой вопрос?
Обратная связь