Tarantool — это база данных и сервер приложений. В данном случае мы будем рассматривать Tarantool именно как базу данных, а в частности, движок для хранения данных в оперативной памяти — memtx. Tarantool — open source-проект: исходный код находится в открытом доступе, что открывает большие возможности для изучения того, как организованы базы данных, а также дает возможность для написания своих решений и их последующего встраивания.

Рассказ пойдет о попытке написать свою структуру данных для поиска (Z-order curve) и её встраивании в существующую экосистему Tarantool.

Данная структура используется для многомерного поиска. Часто в БД для подобных задач применяют R-Tree, но здесь возникло желание реализовать своё экзотическое решение и сравнить его с традиционными подходами. В основе лежит обычное B-дерево, поэтому данный подход должен получиться компактным и быстрым.

В докладе будет рассказано о том, как данный тип индекса был реализован и что из этого получилось. Кроме этого, будут затронуты нюансы работы Tarantool на низком уровне без привязки к конкретной структуре данных — о том, в каком виде физически хранятся внутри Tarantool, как Tarantool работает с данными и как, зная это всё, можно написать свою собственную структуру данных.