Top.Mail.Ru
Индексы | Tarantool
 
Индексы
Индексы

Индексы

Индексы

An index is a special data structure that stores a group of key values and pointers. It is used for efficient manipulations with data.

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

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

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

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

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

It is mandatory to create an index for a space before trying to insert tuples into the space, or select tuples from the space.

The simple index-creation operation is:

box.space.space-name:create_index('index-name')

This creates a unique TREE index on the first field of all tuples (often called «Field#1»), which is assumed to be numeric.

A recommended design pattern for a data model is to base primary keys on the first fields of a tuple. This speeds up tuple comparison due to the specifics of data storage and the way comparisons are arranged in Tarantool.

The simple SELECT request is:

box.space.space-name:select(value)

This looks for a single tuple via the first index. Since the first index is always unique, the maximum number of returned tuples will be 1. You can call select() without arguments, and it will return all tuples. Be careful! Using select() for huge spaces hangs your instance.

An index definition may also include identifiers of tuple fields and their expected types. See allowed indexed field types in section Details about indexed field types:

box.space.space-name:create_index(index-name, {type = 'tree', parts = {{field = 1, type = 'unsigned'}}}

Space definitions and index definitions are stored permanently in Tarantool’s system spaces _space and _index.

Примечание

See full information about creating indexes, such as how to create a multikey index, an index using the path option, or how to create a functional index in our reference for space_object:create_index().

Index operations are automatic: if a data manipulation request changes a tuple, then it also changes the index keys defined for the tuple.

  1. For further demonstrations let’s create a sample space named tester and put it in a variable my_space:

    tarantool> my_space = box.schema.space.create('tester')
    
  2. Format the created space by specifying field names and types:

    tarantool> my_space:format({
             > {name = 'id', type = 'unsigned'},
             > {name = 'band_name', type = 'string'},
             > {name = 'year', type = 'unsigned'},
             > {name = 'rate', type = 'unsigned', is_nullable = true}})
    
  3. Create the primary index (named primary):

    tarantool> my_space:create_index('primary', {
             > type = 'tree',
             > parts = {'id'}
             > })
    

    This is a primary index based on the id field of each tuple.

  4. Insert some tuples into the space:

    tarantool> my_space:insert{1, 'Roxette', 1986, 1}
    tarantool> my_space:insert{2, 'Scorpions', 2015, 4}
    tarantool> my_space:insert{3, 'Ace of Base', 1993}
    tarantool> my_space:insert{4, 'Roxette', 2016, 3}
    
  5. Create a secondary index:

    tarantool> box.space.tester:create_index('secondary', {parts = {{field=3, type='unsigned'}}})
    ---
    - unique: true
      parts:
      - type: unsigned
        is_nullable: false
        fieldno: 3
      id: 2
      space_id: 512
      type: TREE
      name: secondary
    ...
    
  6. Create a multi-part index with three parts:

    tarantool> box.space.tester:create_index('thrine', {parts = {
             > {field = 2, type = 'string'},
             > {field = 3, type = 'unsigned'},
             > {field = 4, type = 'unsigned'}
             > }})
    ---
    - unique: true
      parts:
      - type: string
        is_nullable: false
        fieldno: 2
      - type: unsigned
        is_nullable: false
        fieldno: 3
      - type: unsigned
        is_nullable: true
        fieldno: 4
      id: 6
      space_id: 513
      type: TREE
      name: thrine
    ...
    

There are the following SELECT variations:

  • The search can use comparisons other than equality:

    tarantool> box.space.tester:select(1, {iterator = 'GT'})
    ---
    - - [2, 'Scorpions', 2015, 4]
      - [3, 'Ace of Base', 1993]
      - [4, 'Roxette', 2016, 3]
    ...
    

    The comparison operators are:

    • LT for «less than»
    • LE for «less than or equal»
    • GT for «greater»
    • GE for «greater than or equal» .
    • EQ for «equal»,
    • REQ for «reversed equal»

    Value comparisons make sense if and only if the index type is TREE. The iterator types for other types of indexes are slightly different and work differently. See details in section Iterator types.

    Note that we don’t use the name of the index, which means we use primary index here.

    This type of search may return more than one tuple. The tuples will be sorted in descending order by key if the comparison operator is LT or LE or REQ. Otherwise they will be sorted in ascending order.

  • The search can use a secondary index.

    For a primary-key search, it is optional to specify an index name as was demonstrated above. For a secondary-key search, it is mandatory.

    tarantool> box.space.tester.index.secondary:select({1993})
    ---
    - - [3, 'Ace of Base', 1993]
    ...
    
  • The search can be for all fields, using a table as the value:

    tarantool> box.space.tester.index.thrine:select({'Roxette', 2016, 3})
    ---
    - - [4, 'Roxette', 2016, 3]
    ...
    

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

    tarantool> box.space.tester.index.thrine:select({'Roxette'})
    ---
    - - [1, 'Roxette', 1986, 5]
      - [4, 'Roxette', 2016, 3]
    ...
    

Примечание

You can also add, drop, or alter the definitions at runtime, with some restrictions. Read more about index operations in reference for box.index submodule.

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

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

Характеристика TREE HASH RTREE BITSET
уникальный + + - -
неуникальный + - + +
is_nullable + - - -
может быть многокомпонентным + + - -
многоключевой + - - -
поиск по части ключа + - - -
может быть по первичному ключу + + - -
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-индекс:

  • на вторичный ключ
  • если вы на сто процентов уверены, что его не придется делать неуникальным
  • if you have taken measurements on your data and you see an accountable increase in performance
  • если вы экономите каждый байт на кортежах (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}, {itearator = '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 для индексации 3-мерного, 4-мерного или многомерного пространства используются так же, как и для двухмерного, только пользователь должен указывать больше координат в запросах. Вот небольшой пример использования дерева для 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}} -- insert 4D point
tarantool> my_space:insert{2, {1, 1, 1, 1, 2, 2, 2, 2}} -- insert 4D box

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

Примечание

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

And another frequent mistake is to specify iterator type without quotes, in such way: rtree_index:select(rect, {iterator = 'LE'}). This leads to silent EQ select, because LE is undefined variable and treated as nil, so iterator is unset and default used.

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