Locality preserving dictionaries
Vijayshankar Raman · 1999
We discuss strategies for building locality preserving dictionaries (LPDs) in which all data items within a range lie together, within a space that is a small function of the number of items in the range.We describe an approach where the memory space is partitioned and items are placed in sorted order, with judiciously placed gaps between them, resulting in efficient insert, delete, and search operations.We adapt our algorithms to the particular application of storing database relations on disk via LPDs.By providing a natural clustering mechanism for data in a sorted order instead of simply clustering data at a page granularity, LPDs provide much better I/O performance than traditional clustered indexes on range searches, as well as on access of data in sorted order.Analytical studies of LPDs and clustered B-Trees show that using LPDs results in up to 5 to 13 times faster range searches and sorted order accesses over using a clustered B-Tree, at the expense of 0 to 75% overhead in storage needs and up to 28% overhead in insert/delete costs.