Jump to content United States-English
HP.com Home Products and Services Support and Drivers Solutions How to Buy
» Contact HP
More options
HP.com home
 Programming with Judy: C LanguageJudy Version 4.0 > Chapter 2 The Judy Advantage

Compared with Other Search and Retrieval Methods
» 

Technical documentation

Complete book in PDF
» Feedback
Content starts here

 » Table of Contents

 » Glossary

 » Index

spacerspacerspacer
spacer
spacer
  		 
 

The table below shows how Judy algorithms compare with other search and retrieval methods.

Table 2-1 Title not available (Compared with Other Search and Retrieval Methods)

Search and Retrieval method (data structure)O number
for lookup		Advantages Disadvantages
Arrays Fast indexingPre-allocation of entire array before storing a single element (inefficient for sparse arrays).
HashingDepends on algorithmFast access

  • Synonym management is complex.

  • No near-neighbor lookup capability.

  • Must be tuned for size and nature of data being stored.

Binary TreesO(log n) Gets very deep with large data sets, requiring many memory accesses to reach target values.
AVL Trees
(height-balanced binary trees)		O(log n) 

  • Expensive to keep balanced.

  • May also get very deep with large data sets, requiring many memory accesses to reach target values.

B-treesO(log n) 

  • Slow to access.

  • Inherently difficult to balance.

Skip ListsO(log n)

  • Simplify the tree-balancing problem by using a probabilistic method instead of a strictly enforced balancing method.

  • Their modest improvement in performance (over binary trees) is primarily due to the quaternary, rather than binary, nature of the data structure.

 
Digital Trees (Trie)O (logm n)Fast access

  • Memory inefficient.

  • Requires access times proportional to the number of significant digits of the index value. The access time for storing an index that has a large number of significant digits can be lengthy.

JudyLess than O(log256 n)

  • Fast access times.

  • Grows dynamically on demand.

  • Adjusts in size to the amount of stored data.

  • Minimal number of memory accesses.

  • Depth of tree does not increase significantly with the population of the tree.

  • Very fast lookup times for large sparse arrays.

  • Fast insertion, both average and worst case.

  • Requires no tree rebalancing.

  • External interface is similar to that of a sorted array.

  • Count available.

 

 



Judy Data Structures
  		 


Hashing versus JudyL  
Printable version
Privacy statement Using this site means you accept its terms Feedback to webmaster
© Hewlett-Packard Development Company, L.P.