Fractal
Prefetching B+-Trees: Optimizing Both Cache and Disk Performance
Tuesday November 12, 2002
Hamerschlag Hall D-210
4:00 p.m.
Shimin Chen
Carnegie Mellon University
B+-Trees have been traditionally optimized for I/O performance with disk
pages as tree nodes. Recently, researchers have proposed new types of
B+-Trees optimized for CPU cache performance in main memory environments,
where the tree node sizes are one or a few cache lines. Unfortunately,
due primarily to this large discrepancy in optimal node sizes, existing
disk-optimized B+-Trees suffer from poor cache performance while cache-optimized
B+-Trees exhibit poor disk performance. In this paper, we propose fractal
prefetching B+-Trees (fpB+-Trees), which embed "cache-optimized" trees
within "disk-optimized" trees, in order to optimize both cache and I/O
performance. We design and evaluate two approaches to breaking disk pages
into cache-optimized nodes: disk-first and cache-first. These approaches
are somewhat biased in favor of maximizing disk and cache performance,
respectively, as demonstrated by our results. Both implementations of
fpB+-Trees achieve dramatically better cache performance than disk-optimized
B+-Trees: a factor of 1.1 - 1.8 improvement for search, up to a factor
of 4.2 improvement for range scans, and up to a 20-fold improvement for
updates. In addition, fpB+-Trees accelerate I/O performance for range
scans by using jump-pointer arrays to prefetch leaf pages, thereby achieving
a speed-up of 2.5-5 on IBM's DB2 Universal Database.
|