Making B -Trees Cache Conscious in Main Memory.pdf

《Making B -Trees Cache Conscious in Main Memory.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、MakingB+-TreesCacheConsciousinMainMemoryJunRaoKennethA.RossColumbiaUniversityColumbiaUniversityjunr@cs.columbia.edukar@cs.columbia.eduAbstract+CSB-Treespreallocatespaceforthefullnodegroupandthusreducethesplitcost.OurperformancestudiesPreviousresearchhasshownthat

2、cachebehaviorisim-+showthatCSB-Treesareusefulforawiderangeofportantformainmemoryindexstructures.Cachecon-applications.sciousindexstructuressuchasCacheSensitiveSearchTrees(CSS-Trees)performlookupsmuchfasterthanbinarysearchandT-Trees.However,CSS-Treesare1Introducti

3、ondesignedfordecisionsupportworkloadswithrelatively10000+CPUPerformance(60%/yr)staticdata.AlthoughB-Treesaremorecachecon-DRAMPerformance(10%/yr)sciousthanbinarysearchandT-Trees,theirutilization1000ofacachelineislowsincehalfofthespaceisused100tostorechildpointers.

4、Nevertheless,forapplications+thatrequireincrementalupdates,traditionalB-Trees10performwell.performanceimprovement+OurgoalistomakeB-Treesascacheconscious119801985199019952000asCSS-TreeswithoutincreasingtheirupdatecosttooFigure1:CPU-memoryPerformanceImbalancemuch.W

5、eproposeanewindexingtechniquecalled++CacheSensitiveB-Trees"(CSB-Trees).ItisaAsrandomaccessmemorygetscheaper,itbe-+variantofB-Treesthatstoresallthechildnodesofanycomesincreasinglyaordabletobuildcomputersgivennodecontiguously,andkeepsonlytheaddressofwithlargemain

6、memories.TherecentAsilomartherstchildineachnode.TherestofthechildrencanReport"([BBC+98])predicts:Withintenyears,itbefoundbyaddinganosettothataddress.Sinceonlywillbecommontohaveaterabyteofmainmemoryonechildpointerisstoredexplicitly,theutilizationof+servingasab

7、uerpoolforahundred-terabyteacachelineishigh.CSB-Treessupportincremental+database.AllbutthelargestdatabasetableswillupdatesinawaysimilartoB-Trees.+beresidentinmainmemory."ButmainmemoryWealsointroducetwovariantsofCSB-Trees.+dataprocessingisnotassimpleasincreasingt

8、heSegmentedCSB-Treesdividethechildnodesintobuerpoolsize.Animportantissueiscachebe-segments.Nodeswithinthesamesegmentarestoredcontiguouslyandonlypointerstotheb