У меня есть вопрос - поиск пары значений ключа в индексе - пусть говорят о кассандре или postgres - обычно находится около O (logn)
источник: https://github.com/tinkerpop/blueprints/wiki/Graph-Indices.
В документации redis указано, что сложность выполнения равна O (1).
Источник: http://redis.io/commands/get http://redis.io/commands/hget
И получение значения нескольких ключей является только линейным O (n) http://redis.io/commands/hmget
Как это возможно?
Redis - это хранилище в памяти. Поэтому он может использовать структуры данных, которые адаптированы для хранения данных (что обеспечивает быстрый произвольный доступ).
Чтобы реализовать словари (используемые для основного словаря, но также для хэша и заданных объектов и в сочетании с списком пропусков для объектов zset), Redis использует отдельные цепочки хеш-таблиц, сложность доступа которых равна O (1 + n/k), где n - количество элементов, а k - количество ведер.
Redis гарантирует, что количество ведер растет с количеством элементов, так что на практике n/k остается низким. Эта операция повторной обработки выполняется постепенно в фоновом режиме. Когда количество элементов значимо, сложность близка к O (1) (амортизируется).
Другие магазины (например, Cassandra) предназначены для хранения данных на диске, одновременно сводя к минимуму количество случайных операций ввода-вывода по соображениям производительности. Хэш-таблица не является хорошей структурой данных для этого, потому что она не обеспечивает местность данных (она не очень хорошо подходит для кэширования буфера). Таким образом, на дисковых хранилищах обычно используются варианты деревьев B-tree (большинство RDBMS) или дерева (Lass), которые имеют сложность O (log n).
Итак, Redis предлагает O (1) для многих операций, но есть ограничение: все данные должны вписываться в память. Здесь нет магии.