Комментарии 10
olegrok я рад что получилось закончить прототип. Основное преимущество и назначение индекса — многокритериальный поиск, в приложениях типа yandex.market. Производительность з-кривой деградирует линейно с увеличением числа размерностей, в то время как производительность r-tree — полиномиально. Я бы попробовал протестировать на реальных данных и задачах — проиндексиров базу cian или продуктовый каталог yandex.market. В настоящее время в open source нет субд с хорошей поддержкой многокритериального поиска, связано это в первую очередь с тем что сложно завести транзакционный менеджер для таких индексов. Уверен, что это будет востребованно — вопрос просто доведения технологии до ума и популяризации.
Производительность з-кривой деградирует линейно с увеличением числа размерностей, в то время как производительность r-tree — полиномиально.
Это из чего следует?
В зависимости от переданного ключа мы вычисляем нижнюю и верхнюю границу запроса.
А внутри запроса у вас есть навигация?
Вы же не просто фильтруете диапазон между min/max значениями.
Да, конечно.

Каждая точка проверяется на принадлежность области запроса. Как только мы выходим за её границы, то делаем прыжок в следующую точку вхождения в эту область — github.com/olegrok/tarantool/commit/6f8213e487a1a8b53e83c9f5fe285ffba81af8dd#diff-ef030a57d9a36f0dc3478f8f1d36339bR41

Это функции is_relevant и get_next_zvalue.
Остроумно, кстати. Единственно, при неудачном стечении обстоятельств таких выходов/возвратов может быть очень много.
А вы пытались профилировать работу, смотреть кто занимает процессор?
Да, это правда. На полупустом дереве это неплохо так себя проявляет. В целом графики это и демонстрируют.

Да, perf top показывает, что всё как раз упирается в is_relevant функцию.
image
похожая тема уже поднималась на Хабре, но для небольших размерностей (2-3) и применительно к дисковой БД PostgreSQL
— там кстати и 8 мерный индекс был и 128-мерный.
Если ваше B-дерево имеет страничную организацию, без разницы где находятся страницы — в памяти или на диске.
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Информация

Дата основания
Местоположение
Россия
Сайт
team.mail.ru
Численность
5 001–10 000 человек
Дата регистрации

Блог на Хабре