Индексы

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

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

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

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

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

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

Индексы имеют ряд ограничений. Подробнее см. на странице Ограничения.

Для создания генератора значений индекса можно использовать объект последовательности (sequence). Подробности см. в руководстве.

Не путать с типами индексов — типами структуры данных, являющейся индексом. Подробнее о типах индексов см. ниже.

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

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

Подробнее о типах полей см. в разделе Подробности о типах полей.

У каждого индекса всегда есть тип. Разные типы предназначены для разных сценариев использования.

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

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

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

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

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

Вот несколько рекомендаций.

Не используйте индекс 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'} })

Соответствующее поле кортежа должно быть массивом из 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:

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

 
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}} -- insert 4D pointtarantool> my_space:insert{2, {1, 1, 1, 1, 2, 2, 2, 2}} -- insert 4D boxtarantool> rtree_index:select{1, 2, 3, 4} -- find exact point---- - [1, [1, 2, 3, 4]]...tarantool> rtree_index:select({0, 0, 0, 0, 3, 3, 3, 3}, {iterator = 'LE'}) -- select from 4D box---- - [2, [1, 1, 1, 1, 2, 2, 2, 2]]...tarantool> rtree_index:select({0, 0, 0, 0}, {iterator = 'neighbor'}) -- select neighbours---- - [2, [1, 1, 1, 1, 2, 2, 2, 2]]  - [1, [1, 2, 3, 4]]...

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.