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: 3266
Venue: SIGMOD
Year: 2001
Pagerank: 0.00010483957
Overall Rank: 1,809 | 87.42%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
381	FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs	2010	SIGMOD	0.00024873637
930	Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort	2010	SIGMOD	0.00015238545
1,134	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD	0.00013761456
5,219	Improving Database Performance on Simultaneous Multithreading Processors	2005	VLDB	5.6217069e-05
7,378	Cache-Oblivious Query Processing	2007	CIDR	4.7480163e-05
8,562	Contorting High Dimensional Data for Efficient Main Memory KNN Processing	2003	SIGMOD	4.4937074e-05
9,404	Revisiting B-tree Compression: An Experimental Study	2024	SIGMOD	4.3441378e-05
9,664	A Compact B-tree	2002	SIGMOD	4.3086973e-05
10,368	B-Trees Are Back: Engineering Fast and Pageable Node Layouts	2025	SIGMOD	4.1945683e-05
10,562	FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update	2025	VLDB	4.1945683e-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
9	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.0014279444
52	Database Architecture Optimized for the new Bottleneck: Memory Access	1999	VLDB	0.00066474881
103	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00049150032
174	ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes	1990	VLDB	0.00038347904
233	A Study of Index Structures for Main Memory Database Management Systems	1986	VLDB	0.00032021526
238	Cache Conscious Indexing for Decision-Support in Main Memory	1999	VLDB	0.00031642425
510	Dali: A High Performance Main Memory Storage Manager	1994	VLDB	0.00021390381
3,755	In-Memory Data Management for Consumer Transactions: The TimesTen Approach	1999	SIGMOD	6.784193e-05
5,886	Logical and Physical Versioning in Main Memory Databases	1997	VLDB	5.2880714e-05
7,908	DataBlitz Storage Manager: Main-Memory Database Performance for Critical Applications	1999	SIGMOD	4.620568e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,411	Towards Efficient Main-Memory Use For Optimum Tree Index Update	2008	VLDB	4.1945683e-05
6,229	When Tree Meets Hash: Reducing Random Reads for Index Structures on Persistent Memories	2023	SIGMOD	5.1463389e-05
11,822	Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries	2016	PODS	4.1945683e-05
1,375	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.00012303141
1,983	Optimizing Multidimensional Index Trees for Main Memory Access	2001	SIGMOD	9.8638201e-05
2,244	Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems	2001	VLDB	9.2097912e-05
1,312	Reducing the Storage Overhead of Main-Memory OLTP Databases with Hybrid Indexes	2016	SIGMOD	0.00012652548
531	Improving Index Performance through Prefetching	2001	SIGMOD	0.00020790058
1,195	Buffering Accesses to Memory-Resident Index Structures	2003	VLDB	0.00013406526
233	A Study of Index Structures for Main Memory Database Management Systems	1986	VLDB	0.00032021526