Editing Judy array

{{Short description|Type of associative array}}
{{notability|date=April 2022}}
In [[computer science]], a '''Judy array''' is a [[data structure]] implementing a type of [[associative array]] with high performance and low memory usage.<ref>[https://patents.google.com/patent/US6735595B2/en Robert Gobeille and Douglas Baskins' patent]</ref> Unlike most other [[key-value store]]s, 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'').<ref>{{Cite web|url=http://packages.debian.org/buster/libjudy-dev|title=Debian -- Details of package libjudy-dev in buster}}</ref> Roughly speaking, Judy arrays are highly optimized 256-ary [[radix tree]]s.<ref>Alan Silverstein, "[http://judy.sourceforge.net/application/shop_interm.pdf Judy IV Shop Manual]", 2002</ref>

Judy trees are usually faster than [[AVL tree]]s, [[B-tree]]s, [[hash table]]s and [[skip list]]s 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.<ref>{{Cite web|url=http://judy.sourceforge.net/doc/10minutes.htm|title=A 10-Minute Description of How Judy Arrays Work and Why They Are So Fast}}</ref>

==History==
The Judy array was invented by Douglas Baskins and named after his sister.<ref name="judy.sourceforge.net">{{cite web |url=http://judy.sourceforge.net/ |title=Home |website=judy.sourceforge.net}}</ref>

==Benefits==
===Memory allocation===
Judy arrays are [[Dynamic array|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.

===Speed===
Judy arrays are designed to minimize the number of expensive [[cache-line]] fills from [[random-access memory|RAM]], and so the algorithm contains much complex logic to avoid cache misses as often as possible. Due to these [[CPU cache|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.<ref name="nothings">{{Cite web|url=http://www.nothings.org/computer/judy/|title = A performance comparison of Judy to hash tables}}</ref>

==Drawbacks==
Judy arrays are extremely complicated. The smallest implementations are thousands of lines of code.<ref name="judy.sourceforge.net"/> In addition, Judy arrays are optimized for machines with 64 byte cache lines, making them essentially unportable without a significant rewrite.<ref name="nothings"/>

==See also==
* [[Radix tree]]
* [[Hash array mapped trie]]

==References==
{{reflist}}

==External links==
*[http://judy.sourceforge.net/ Main Judy arrays site]
*[http://judy.sourceforge.net/downloads/10minutes.htm How Judy arrays work and why they are so fast]
*[http://judy.sourceforge.net/application/shop_interm.pdf A complete technical description of Judy arrays]
*[http://www.nothings.org/computer/judy/ An independent performance comparison of Judy to Hash Tables]
*[https://github.com/JerrySievert/judyarray A compact implementation of Judy arrays in 1250 lines of C code]

[[Category:Associative arrays]]