Рубрика «nosql» - 33

От переводчика:
Хочу представить вашему вниманию перевод ответа одного из разработчиков Redis, на вопрос о том, какие структуры данных используются внутри Redis. Оригинальную дискуссию вы можете найти на stackoverflow.

Я попробую ответить на вопрос, но начну с того, что на первый взгляд может показаться странным: если вы не интересуетесь внутренностями Redis, вы не должны заботиться о том, как реализованы структуры данных изнутри. Причина этому проста — сложность каждой команды Redis вы можете найти в документации, и если у вас есть набор операций и их вычислительная сложность, то единственное, что вам нужно, это некоторое представление об использовании памяти (и потому, что мы делаем много оптимизаций, в зависимости от данных, лучший способ получить эти последние цифры это тесты в реальных условиях)

Но поскольку вы спросили, вот внутренние реализации каждой структуры данных Redis:

• Строки реализованы с использованием библиотеки динамических строк C, так что мы не платим (говоря асимптотически) за выделение памяти в операциях добавления. Таким образом мы получаем сложность добавления O(N), вместо, например, квадратичной.
• Списки реализованы как связные списки.
• Множества и Хэши реализованы как хэш-таблицы.
• Упорядоченные множества реализованы как списки с пропусками (особый тип сбалансированных деревьев)

Читать полностью »