Improving index performance through prefetching

This paper proposes and evaluates Prefetching B+-Trees (pB(+)-Trees), which use prefetching to accelerate two important operations on BS-Tree indices: searches and, range scans. To accelerate searches, pB(+)-Trees use prefetc hing to effectively create wider nodes than the natural data transfer size: e.g., eight vs, one cache lines or disk pages. These wider nodes reduce th e height of the B+-Tree, thereby decreasing the number of expensive misses when going;from parent to child without significantly increasing the cost o f fetching a given node. Our results show that this technique speeds up sea rch and update times by a factor of 1.2-1.5 for main-memory B+-Trees. In ad dition, it outperforms and is complementary to "Cache-Sensitive B+-Trees." To accelerate range scans, pB(+)-Trees provide arrays df pointers to their leaf nodes. These allow the pB(+)-Tree to prefetch arbitrarily far ahead, e ven for nonclustered indices, thereby hiding the normally expensive cache m isses associated with traversing the leaves within the range. Our results s how that this technique yields over a sixfold speedup on range scans of 100 0+ keys. Although our experimental evaluation focuses on main memory databa ses, the techniques that we propose are also applicable to hiding disk late ncy.