Top.Mail.Ru
Индексы | Tarantool
Tarantool
Узнайте содержание релиза 2.8
Индексы

Индексы

Индексы

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

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

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

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

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

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

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

Простая операция по созданию индекса выглядит следующим образом:

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

При этом создается уникальный TREE-индекс по первому полю всех кортежей (обычно его называют «Field#1»). Предполагается, что индексируемое поле является числовым.

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

Вот простой запрос SELECT:

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

Такой запрос ищет отдельный кортеж, используя первичный индекс. Поскольку первичный индекс всегда уникален, то данный запрос вернет не более одного кортежа. Можно также вызвать select() без аргументов, чтобы вернуть все кортежи. Осторожно! Если вызвать select() без аргументов в огромном спейсе, ваш экземпляр зависнет.

Определение индекса может также содержать идентификаторы полей кортежа и их предполагаемые типы. См. допустимые типы полей в разделе Описание типов индексируемых полей:

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

Определения спейса и определения индексов хранятся в системных спейсах Tarantool _space и _index соответственно.

Примечание

Полную информацию о создании индексов, например о создании индексов по массиву (multikey), индексов с использованием пути path или функциональных индексов см. в справочнике space_object:create_index().

Операции с индексами производятся автоматически. Если запрос на изменение данных меняет данные в кортеже, то изменятся и ключи индекса для данного кортежа.

  1. Для примера создадим спейс с именем tester и поместим его в переменную my_space:

    tarantool> my_space = box.schema.space.create('tester')
    
  2. Отформатируем созданный спейс, указав имена и типы полей:

    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. Создадим первичный индекс с именем primary:

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

    Это первичный индекс по полю id в каждом кортеже.

  4. Вставим несколько кортежей в спейс:

    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. Создадим вторичный индекс:

    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. Создадим составной индекс (multi-part) из трех частей:

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

Можно использовать такие варианты SELECT:

  • Помимо условия равенства, при поиске могут использоваться и другие условия сравнения:

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

    Есть такие операторы сравнения:

    • LT — «меньше»
    • LE — «меньше или равно»
    • GT — «больше»
    • GE — «больше или равно»
    • EQ — «равно»,
    • REQ — «равно, результаты отсортированы в порядке убывания по ключу»

    Только для TREE-индексов есть смысл в сравнении значений. Итераторы для других типов индексов немного отличаются и работают по-другому. Более подробную информацию см. в разделе Типы итераторов.

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

    Этот вариант поиска может вернуть более одного кортежа. Если используется оператор сравнения LT, LE или REQ, то кортежи будут отсортированы по ключу в порядке убывания. Во всех остальных случаях — в порядке возрастания.

  • Для поиска можно использовать вторичный индекс.

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

    tarantool> box.space.tester.index.secondary:select({1993})
    ---
    - - [3, 'Ace of Base', 1993]
    ...
    
  • Поиск можно производить по всем полям через запись в виде таблицы:

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

Примечание

С некоторыми ограничениями можно добавлять, удалять или изменять определения во время исполнения кода. Более подробную информацию об операциях с индексами см. в справочнике по вложенному модулю box.index.

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

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

Характеристика 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]]
...

Примечание

Keep in mind that select NEIGHBOR iterator with unset limits extracts the entire space in order of increasing distance. And there can be tons of data, and this can affect the performance.

Другая типичная ошибка — указать тип итератора без кавычек следующим образом: 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-индексов в порядке по убыванию.