TY - GEN
T1 - Cache-oblivious string B-trees
AU - Bender, Michael A.
AU - Farach-Colton, Martin
AU - Kuszmaul, Bradley C.
PY - 2006
Y1 - 2006
N2 - B-trees are the data structure of choice for maintaining searchable data on disk. However, B-trees perform suboptimally when keys are long or of variable length,when keys are compressed, even when using front compression, the standard B-tree compression scheme,for range queries, andwith respect to memory effects such as disk prefetching.This paper presents a cache-oblivious string B-tree (COSB-tree) data structure that is efficient in all these ways: The COSB-tree searches asymptotically optimally and inserts and deletes nearly optimally.It maintains an index whose size is proportional to the front-compressed size of the dictionary. Furthermore, unlike standard front-compressed strings, keys can be decompressed in a memory-efficient manner.It performs range queries with no extra disk seeks; in contrast, B-trees incur disk seeks when skipping from leaf block to leaf block.It utilizes all levels of a memory hierarchy efficiently and makes good use of disk locality by using cache-oblivious layout strategies.
AB - B-trees are the data structure of choice for maintaining searchable data on disk. However, B-trees perform suboptimally when keys are long or of variable length,when keys are compressed, even when using front compression, the standard B-tree compression scheme,for range queries, andwith respect to memory effects such as disk prefetching.This paper presents a cache-oblivious string B-tree (COSB-tree) data structure that is efficient in all these ways: The COSB-tree searches asymptotically optimally and inserts and deletes nearly optimally.It maintains an index whose size is proportional to the front-compressed size of the dictionary. Furthermore, unlike standard front-compressed strings, keys can be decompressed in a memory-efficient manner.It performs range queries with no extra disk seeks; in contrast, B-trees incur disk seeks when skipping from leaf block to leaf block.It utilizes all levels of a memory hierarchy efficiently and makes good use of disk locality by using cache-oblivious layout strategies.
KW - Cache oblivious string B-tree
KW - Locality preserving front compression
KW - Packed-memory array
KW - Range query
KW - Rebalance
UR - http://www.scopus.com/inward/record.url?scp=34250689978&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34250689978&partnerID=8YFLogxK
U2 - 10.1145/1142351.1142385
DO - 10.1145/1142351.1142385
M3 - Conference contribution
AN - SCOPUS:34250689978
SN - 1595933182
SN - 9781595933188
T3 - Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
SP - 233
EP - 242
BT - Proceedings of the Twenty-Fifth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2006
T2 - 25th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2006
Y2 - 26 June 2006 through 28 June 2006
ER -