Fractal Tree Indexes Theory and Practice.pdf

《Fractal Tree Indexes Theory and Practice.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、FractalTree®IndexesTheoryandPracticeTimCallaghanVP/Engineering,Tokutektim@tokutek.com@tmcallaghan®Tuesday,May14,13WhoamI?“MarkCallaghan’slesser-knownbutnonethelesssmartbrother.”[C.Monash,May2010]www.dbms2.com/2010/05/25/voltdb-finally-launches®Tuesday,May14,13PleaseAskQuestions.®Tuesday,May14,13

2、FractalTreeIndexesTheory®Tuesday,May14,13•Atahighlevel•B-trees•InnoDBstorage•TokuDBstorage•MongoDBstorageI’mgoingtocoververysimplescenarios(nosplittingormerging)®Tuesday,May14,13B-trees®Tuesday,May14,13B-treeOverviewIwilluseasimplesingle-pivotexamplethroughoutthispresentation®Tuesday,May14,13B-t

3、reeOverview-vocabularyPivotsPointersInternalNodes-PathtodataLeafNodes-ActualData®Tuesday,May14,13B-treeOverview-example2210992,3,410,2022,2599*PivotRuleis>=®Tuesday,May14,13B-treeOverview-search“Find25”2210992,3,410,2022,2599®Tuesday,May14,13B-treeOverview-insert“Insert15”2210992,3,410,15,2022,2

4、599®Tuesday,May14,13B-treeOverview-storagePerformanceisIOlimitedwhenbiggerthanRAM:trytofitallinternalnodesandsomeleafnodesRAM221099RAMDISK2,3,410,2022,2599®Tuesday,May14,13InnoDBStorage®Tuesday,May14,13InnoDBB-trees-primarykey251099(2,12,22),(4,4,1)(10,12,5),(25,18,9)(99,5555,2)(20,-5,4)storefull

5、rowsinleafnodesuseprimarykeyfororderingexample:tablet(aintprimarykey,bint,cint)®Tuesday,May14,13InnoDBB-trees-secondarykeys1845555(-5,20)(4,4),(12,10),(18,25)(5555,99)(12,2)eachsecondarykeycreatesanotherB-treeusesecondarykeyfororderingPKisstoredaswell®Tuesday,May14,13InnoDBB-trees-searchselect*f

6、romtwhereb=12;(a)secondaryindex-findrowsforb=12(getPKs)(b)PKindex-get*forPK=10and21825455551099(-5,20)(4,4),(18,25)(5555,99)(2,12,22),(10,12,5),(25,18,9)(99,5555,2(12,10),(4,4,1)(20,-5,4)(12,2)®Tuesday,May14,13InnoDBB-trees-insertinsertintotvalues(8,9,10);(a)insertintoleafifinmemory,bufferifnot(b

7、)insertintoleafnodeinPKindex1825(9,8)455551099(-5,20)(4,4),(18,25)(5555,99)(2,12,22),(10,12,5),(25,18,9)(99,5555,2(12,10),(4,4,1),(20,-5,4)(12,2)(8,9.10)®Tuesday,May14,13InnoDBB-trees-secondarykeybufferinsert/update/deletebu