Fractal-Tree-Technology-and-the-Art-of-Indexing

《Fractal-Tree-Technology-and-the-Art-of-Indexing》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、®FractalTreeTechnologyOverviewTheArtofIndexingMartínFarach-ColtonCo-founder&ChiefTechnologyOfficerNotallindexingisthesameB-treeisthebasisforalmostallDBsystems•Datastructureinventedin1972•Hasnotkeptupwithhardwaretrends‣Workspoorlyonmodernrotationaldisk

2、s‣WorkspoorlyonSSDFractalTreeIndexesisthebasisofTokuDB•Scaleswithhardware•FastIndexing➔MoreIndexing➔FasterQueries•GreatCompression•NoFragmentation•ReducedwearonSSDsTheArtofIndexing®HowdoFractalTreeIndexesoutperformB-trees?HowdoFractalTreeIndexesoutper

3、formB-trees?First,somefactsaboutstoragesystemsStorageisquirkyHarddisksareslowforrandomI/ObutfastforsequentialI/ODifferencecausesproblemslikefragmentation,...TheArtofIndexing®StorageisquirkyHarddisksareslowforrandomI/ObutfastforsequentialI/OSSDsarefast

4、forDifferencecausesproblemsrandomI/Obutexpensiveforlikefragmentation,...sequential.Garbagecollectioncausesartefacts:increasedwear,writecliffs...TheArtofIndexing®Storage♡BigReadsandWritesBigI/OsTheArtofIndexing®Storage♡BigReadsandWritesHardDisks:NoFrag

5、mentationBigI/OsTheArtofIndexing®Storage♡BigReadsandWritesHardDisks:NoFragmentationSSDs:LessGarbageCollection&WearBigI/OsTheArtofIndexing®Storage♡BigReadsandWritesHardDisks:NoFragmentationSSDs:LessGarbageCollection&WearBigI/OsButyouonlygetthegoodiesif

6、eachI/OhaslotsofnewbytesTheArtofIndexing®Storage♡BigReadsandWritesHardDisks:NoFragmentationSSDs:LessGarbageCollection&WearBigI/OsButyouonlygetthegoodiesifeachI/OhaslotsofnewbytesIfyoureadabigblock,changeonebyte,thenwriteit,yougetterriblewearproblemsTh

7、eArtofIndexing®Storage♡BigReadsandWritesHardDisks:NoFragmentationSSDs:LessGarbageCollection&WearBigI/OsBoth:BetterButyouonlygetthegoodiesifCompressioneachI/OhaslotsofnewbytesIfyoureadabigblock,changeonebyte,thenwriteit,yougetterriblewearproblemsTheArt

8、ofIndexing®Dataisbig,RAMisSmallCachingisgreat•Butyoucan’tcacheallyourdata•Forstuffnotinmemory,youhavetogotodiskGoal:DothebestwecanforthestuffondiskRAMDataTheArtofIndexing®Now,What’saB-tree?&aFractalTreeIndexWhat’saB-tree?BSearchTreeBBB......BB