Джуди-массив: Высокопроизводительная ассоциативная структура данных
Judy array
Джуди-массив: высокопроизводительная ассоциативная структура данных без хеширования. Эффективно сжимает ключи, экономит память, масштабируется до петабайтов.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Тип ассоциативного массива
Type of associative array
В информатике, Judy-массив — это структура данных, реализующая тип ассоциативного массива с высокой производительностью и низким потреблением памяти. В отличие от большинства других хранилищ ключ-значение, Judy-массивы не используют хеширование, применяют сжатие к своим ключам (которые могут быть целыми числами или строками) и могут эффективно представлять разреженные данные; то есть они могут иметь большие диапазоны неназначенных индексов без существенного увеличения использования памяти или времени обработки. Они разработаны для сохранения эффективности даже при размерах структур в диапазоне пета-элементов, с масштабированием производительности порядка O(log n). По сути, Judy-массивы — это высокооптимизированные 256-ичные радикс-деревья. Judy-деревья обычно быстрее, чем AVL-деревья, B-деревья, хеш-таблицы и списки пропусков, поскольку они оптимизированы для максимального использования кэша процессора. Кроме того, им не требуется балансировка дерева и не используется алгоритм хеширования.
In computer science, a Judy array is a data structure implementing a type of associative array with high performance and low memory usage. Unlike most other key value stores, Judy arrays use no hashing, leverage compression on their keys (which may be integers or strings), and can efficiently represent sparse data; that is, they may have large ranges of unassigned indices without greatly increasing memory usage or processing time. They are designed to remain efficient even on structures with sizes in the peta element range, with performance scaling on the order of O(log n). Roughly speaking, Judy arrays are highly optimized 256 ary radix trees. Judy trees are usually faster than AVL trees, B trees, hash tables and skip lists because they are highly optimized to maximize usage of the CPU cache. In addition, they require no tree balancing and no hashing algorithm is used.
История
Массив Джуди был изобретен Дугласом Баскинсом и назван в честь его сестры.
The Judy array was invented by Douglas Baskins and named after his sister.
Распределение памяти
Массивы Джуди динамичны и могут увеличиваться или уменьшаться по мере добавления или удаления элементов. Объем памяти, используемый массивами Джуди, почти пропорционален числу элементов в массиве.
Judy arrays are dynamic and can grow or shrink as elements are added to, or removed from, the array. The memory used by Judy arrays is nearly proportional to the number of elements in the Judy array.
Скорость
Массивы Джуди разработаны для минимизации числа дорогостоящих операций заполнения кэш-линий из оперативной памяти, поэтому алгоритм содержит сложную логику, чтобы максимально избежать промахов кэша. Благодаря этим оптимизациям кэша, массивы Джуди работают быстро, особенно с очень большими наборами данных. На последовательных или почти последовательных наборах данных массивы Джуди могут даже превосходить хэш-таблицы, поскольку, в отличие от них, внутренняя древовидная структура массивов Джуди сохраняет порядок ключей.
Judy arrays are designed to minimize the number of expensive cache line fills from RAM, and so the algorithm contains much complex logic to avoid cache misses as often as possible. Due to these cache optimizations, Judy arrays are fast, especially for very large datasets. On data sets that are sequential or nearly sequential, Judy arrays can even outperform hash tables, since, unlike hash tables, the internal tree structure of Judy arrays maintains the ordering of the keys.
Недостатки
Схемы Джуди крайне сложны. Даже самые простые реализации насчитывают тысячи строк кода. Более того, схемы Джуди оптимизированы для машин с кэш-линиями размером 64 байта, что делает их практически непереносимыми без существенной переработки.
Judy arrays are extremely complicated. The smallest implementations are thousands of lines of code. In addition, Judy arrays are optimized for machines with 64 byte cache lines, making them essentially unportable without a significant rewrite.