Making B+- trees cache conscious in main memory

By Jun Rao, K. A. Ross. ACM SIGMOD Conference, 2000

509 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Hardware and Architecture

View Paper: https://www.semanticscholar.org/paper/e542bb567661be100fe983209f223146ab437520

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Hardware and Architecture

Citations in the corpus

Evaluating window joins over unbounded streams (2003, unknown): “L1, L2 cache) utilization characteristics [22][23].”
Persistent B+-Trees in Non-Volatile Main Memory (2015, background): “Therefore, line 1 reflects the states after the insertion but line 2 reflects the states before the insertion.”
Implementing database operations using SIMD instructions (2002, background): “Various techniques for organizing index structures to be sensitive to modern architectures have been proposed, with particular emphasis on cache performance [21, 22, 11, 6, 17].”
FPTree: A Hybrid SCM-DRAM Persistent and Concurrent B-Tree for Storage Class Memory (2016, methodology): “Following another approach, Yang et al. [28] proposed the NV-Tree , a persistent and concurrent B-Tree based on the CSB + -Tree [23].”
FAST: fast architecture sensitive tree search on modern CPUs and GPUs (2010, methodology): “Later, they applied cache consciousness to B+-trees and proposed a CSB+-tree [26] to support efficient updates.”
In-Memory Big Data Management and Processing: A Survey (2015, background): “Index cache consciousness, time/space efficiency T-Tree [80], CSS-Trees [81], CSB-Trees [82], ∆-Tree [83], BD-Tree [84], FAST [85], ART [87] Data Layout cache consciousness, space efficiency PAX [91], columnar layout [41], [88], HANA Hybrid Store [74], slab allocator [61], logstructure [75] Parallel”
The adaptive radix tree: ARTful indexing for main-memory databases (2013, unknown): “As an alternative, they proposed a cache conscious B-tree variant, the CSB-tree [12].”
Cache craftiness for fast multicore key-value storage (2012, background): “Rao et al. [30] propose storing each node’s children in contiguous memory to make better use of cache.”
ALEX: An Updatable Adaptive Learned Index (2019, background): “CSB-tree [31] extends the static CSS-trees by supporting incremental updates without sacricing CPU cache performance.”
The Case for Learned Index Structures (2017, methodology): “As the original main-memory trees had poor cache behavior, several cache conscious B+-tree variants were proposed, such as the CSB+-tree [58].”
OLTP through the looking glass, and what we found there (2008, methodology): “In such systems, optimized indices [RR99, RR00 ] as well as eschewing disk-optimized tuple formats and page layouts (or lack thereof) [GS92] are important to consider.”