Индексы

TREE-индексы

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

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

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

HASH-индексы

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

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

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

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

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

RTREE-индексы

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]]
...

BITSET-индексы

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-индексов в порядке по убыванию.