Improving index performance through prefetching

摘要: This paper proposes and evaluate Prefetching B+-Trees (pB+-Trees), which use prefetching to accelerate two important operations on B+-Tree indices: searches range scans. To searches, pB+-Trees effectively create wider nodes than the natural data transfer size: e.g., eight vs. one cache lines or disk pages. These reduce height of B+-Tree, thereby decreasing number expensive misses when going from parent child without significantly increasing cost fetching a given node. Our results show that this technique speeds up search update times by factor 1.21-1.5 for main-memory B+-Trees. In addition, it outperforms is complementary “Cache-Sensitive B+-Trees.” scans, provide arrays pointers their leaf nodes. allow pB+-Tree prefetch arbitrarily far ahead, even nonclustered indices, hiding normally associated with traversing leaves within range. yields over sixfold speedup scans 1000+ keys. Although our experimental evaluation focuses main memory databases, techniques we propose are also applicable latency.