Our goal is to provide faster lookup times than binary search by paying attention to reference locality and cache behavior, without using substantial extra space. We propose a new indexing technique called ``Cache-Sensitive Search Trees'' (CSS-trees). Our technique stores a directory structure on top of a sorted array. Nodes in this directory have size matching the cache-line size of the machine. We store the directory in an array and do not store internal-node pointers; child nodes can be found by performing arithmetic on array o sets.

We compare the algorithms based on their time and space requirements. We have implemented all of the techniques, and present a performance study on two popular modern machines. We demonstrate that with a small space overhead, we can reduce the cost of binary search on the array by more than a factor of two. We also show that our technique dominates B+-trees, T-trees, and binary search trees in terms of both space and time. A cache simulation verifies that the gap is due largely to cache misses.

[AHK85]

...

[BBC+98]

Philip A. Bernstein , Michael L. Brodie , Stefano Ceri , David J. DeWitt , Michael J. Franklin , Hector Garcia-Molina , Jim Gray , Gerald Held , Joseph M. Hellerstein , H. V. Jagadish , Michael Lesk , David Maier , Jeffrey F. Naughton , Hamid Pirahesh , Michael Stonebraker , Jeffrey D. Ullman : The Asilomar Report on Database Research. SIGMOD Record 27(4) : 74-80(1998)

[CLH98]

...

[Com79]

Douglas Comer : The Ubiquitous B-Tree. Computing Surveys 11(2) : 121-137(1979)

[CS83]

Francesca Cesarini , Giovanni Soda : An Algorithm to Construct a Compact B-Tree in Case of Ordered Keys. IPL 17(1) : 13-16(1983)

[Eng98]

...

[Fre95]

Clark D. French : ``One Size Fits All'' Database Architectures Do Not Work for DDS. SIGMOD Conference 1995 : 449-450

[Fre97]

Clark D. French : Teaching an OLTP Database Kernel Advanced Data Warehousing Techniques. ICDE 1997 : 194-198

[GBC98]

Goetz Graefe , Ross Bunker , Shaun Cooper : Hash Joins and Hash Teams in Microsoft SQL Server. VLDB 1998 : 86-97

[GMS86]

...

[GR93]

Jim Gray , Andreas Reuter : Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents

[Hag86]

Robert B. Hagmann : Crash Recovery Scheme for a Memory-Resident Database System. IEEE Transactions on Computers 35(9) : 839-843(1986)

[Inc99]

...

[JLRS94]

H. V. Jagadish , Daniel F. Lieuwen , Rajeev Rastogi , Abraham Silberschatz , S. Sudarshan : Dalí: A High Performance Main Memory Storage Manager. VLDB 1994 : 48-59

[JTR87]

Wiebren de Jonge , Andrew S. Tanenbaum , Reind P. van de Riet : Two Access Methods Using Compact Binary Trees. TSE 13(7) : 799-810(1987)

[Knu73]

Donald E. Knuth : The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X

[LC86a]

Tobin J. Lehman , Michael J. Carey : Query Processing in Main Memory Database Management Systems. SIGMOD Conference 1986 : 239-250

[LC86b]

Tobin J. Lehman , Michael J. Carey : A Study of Index Structures for Main Memory Database Management Systems. VLDB 1986 : 294-303

[LC87]

Tobin J. Lehman , Michael J. Carey : A Recovery Algorithm for A High-Performance Memory-Resident Database System. SIGMOD Conference 1987 : 104-117

[LL96]

Anthony LaMarca , Richard E. Ladner : The Influence of Caches on the Performance of Heaps. ACM Journal of Experimental Algorithms 1 : 4(1996)

[LL97]

Anthony LaMarca , Richard E. Ladner : The Influence of Caches on the Performance of Sorting. SODA 1997 : 370-379

[LN88]

Kai Li , Jeffrey F. Naughton : Multiprocessor Main Memory Transaction Processing. DPDS 1988 : 177-187

[LSC92]

Tobin J. Lehman , Eugene J. Shekita , Luis-Felipe Cabrera : An Evaluation of Starburst's Memory Resident Storage Component. TKDE 4(6) : 555-566(1992)

[NBC+94]

Chris Nyberg , Tom Barclay , Zarka Cvetanovic , Jim Gray , David B. Lomet : AlphaSort: A RISC Machine Sort. SIGMOD Conference 1994 : 233-242

[Pet57]

...

[SAC+79]

Patricia G. Selinger , Morton M. Astrahan , Donald D. Chamberlin , Raymond A. Lorie , Thomas G. Price : Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979 : 23-34

[SKN94]

Ambuj Shatdal , Chander Kant , Jeffrey F. Naughton : Cache Conscious Algorithms for Relational Query Processing. VLDB 1994 : 510-521

[Smi82]

Alan Jay Smith : Cache Memories. Computing Surveys 14(3) : 473-530(1982)

[Sof97]

...

[Syb97]

...

[WK90]

Kyu-Young Whang , Ravi Krishnamurthy : Query Optimization in a Memory-Resident Domain Relational Calculus Database System. TODS 15(1) : 67-95(1990)

[WL91]

Michael E. Wolf , Monica S. Lam : A Data Locality Optimizing Algorithm. PLDI 1991 : 30-44