基于不規(guī)則碎片預(yù)取的B+樹的Cache/Disk性能優(yōu)化技術(shù)
(Fractal Prefetching B++ Trees:
Optimizing Both Cache and Disk Performance)

全文16頁 約7600字 論述翔實(shí)

摘要：
B+樹通常情況下采用將磁盤頁(disk pages)作為結(jié)點(diǎn)的方式用于優(yōu)化I/O執(zhí)行性能。最近，研究人員提出用一種新型的以一個(gè)至多個(gè)Cache 塊(Cache Lines) 為結(jié)點(diǎn)的B+樹來優(yōu)化主存環(huán)境下的CPU Cache的性能。不幸的是，由于在優(yōu)化結(jié)點(diǎn)體積上的巨大差異，現(xiàn)有的磁盤優(yōu)化B+樹在Cache優(yōu)化方面的效果極差，同樣Cache優(yōu)化B+樹在磁盤優(yōu)化方面的效果也不好。為此，我們（本文的作者，下同）提出一種基于碎片預(yù)取的B+樹(fractal prefetching B+ Trees, 又稱fpB+ Trees)，已達(dá)到能同時(shí)優(yōu)化Cache 和I/O的目的。我們?cè)O(shè)計(jì)并評(píng)估了兩種將磁盤頁分解為優(yōu)化的Cache結(jié)點(diǎn)(Cache-optimized nodes)的方法：disk-first法和Cache-first法。我們的結(jié)果驗(yàn)證表明：這兩種方法在優(yōu)化Cache性能方面都比磁盤優(yōu)化B+樹(disk-optimized B+ Trees)的效果要好得多。另外，由于采用了跳躍指針(jump-pointer)數(shù)組來預(yù)取頁結(jié)點(diǎn)，fpB+樹使得I/O中區(qū)間掃描(range scans)的性能得到提高。