Main-Memory Index Structures with Fixed-Size Partial Keys

Summary: Introduces pkT-trees and pkB-trees for main-memory OLTP by storing fixed-size partial-keys in internal nodes to reduce cache misses. Shows that a tiny key fragment suffices to avoid most misses, enabling simple node layouts and competitive performance against other main-memory trees across diverse key sizes. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h4645a3043d688d56
Venue: SIGMOD
Year: 2001
Pagerank: 9.5284548e-05
Overall Rank: 1,839 | 87.65%
DOI: 10.1145/375663.375681

Incoming Non-self Citations Over Time

Authors

1. Philip Bohannon (AT&T)
2. Peter McIlroy (AT&T)
3. Rajeev Rastogi (AT&T)

BibTeX Citation

@inproceedings{bohannon_sigmod01,
        title = {{Main-Memory Index Structures with Fixed-Size Partial Keys}},
        author = {Bohannon, Philip and McIlroy, Peter and Rastogi, Rajeev},
        series = {{SIGMOD} '01},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/375663.375681},
        url = {https://dl.acm.org/doi/10.1145/375663.375681},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
277	FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs	2010	SIGMOD	0.00022320139
663	Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort	2010	SIGMOD	0.00014997516
910	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD	0.00013122392
4,873	Improving Database Performance on Simultaneous Multithreading Processors	2005	VLDB	6.370725e-05
7,920	Cache-Oblivious Query Processing	2007	CIDR	5.4250739e-05
8,935	Contorting High Dimensional Data for Efficient Main Memory KNN Processing	2003	SIGMOD	5.2534908e-05
9,295	Revisiting B-tree Compression: An Experimental Study	2024	SIGMOD	5.2003819e-05
9,559	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD	5.1577035e-05
9,982	A Compact B-tree	2002	SIGMOD	5.1008099e-05
11,245	FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update	2025	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
7	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.00081971778
27	Database Architecture Optimized for the New Bottleneck: Memory Access	1999	VLDB	0.00051576613
68	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00037957995
206	Cache Conscious Indexing for Decision-Support in Main Memory	1999	VLDB	0.00024981343
221	ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes	1990	VLDB	0.00024269058
229	A Study of Index Structures for Main Memory Database Management Systems	1986	VLDB	0.00023915204
820	Dali: A High Performance Main Memory Storage Manager	1994	VLDB	0.00013658052
4,034	In-Memory Data Management for Consumer Transactions: The TimesTen Approach	1999	SIGMOD	6.8366873e-05
5,921	Logical and Physical Versioning in Main Memory Databases	1997	VLDB	5.9454117e-05
8,313	DataBlitz Storage Manager: Main-Memory Database Performance for Critical Applications	1999	SIGMOD	5.3557762e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,901	Towards Efficient Main-Memory Use For Optimum Tree Index Update	2008	VLDB
2	6,070	When Tree Meets Hash: Reducing Random Reads for Index Structures on Persistent Memories	2023	SIGMOD
3	12,326	Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries	2016	PODS
4	768	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD
5	2,019	Optimizing Multidimensional Index Trees for Main Memory Access	2001	SIGMOD
6	1,716	Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems	2001	VLDB
7	960	Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes	2016	SIGMOD
8	547	Improving Index Performance through Prefetching	2001	SIGMOD
9	1,105	Buffering Accesses to Memory-Resident Index Structures	2003	VLDB
10	229	A Study of Index Structures for Main Memory Database Management Systems	1986	VLDB