资源描述：
《Performance of Fractal tree databases.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、PerformanceofFractal-TreeDatabasesMichaelA.BenderTheProblemProblem:maintainadynamicdictionaryondisk.Motivation:filesystems,databases,etc.Stateoftheart:•B-tree[Bayer,McCreight72]•cache-obliviousB-tree[Bender,Demaine,Farach-Colton00]•buffertree[Arge95]•buffered-repositor
2、ytree[Buchsbaum,Goldwasser,Venkatasubramanian,Westbrook00]•Bεtree[Brodal,Fagerberg03]•log-structuredmergetree[O'Neil,Cheng,Gawlick,O'Neil96]•stringB-tree[Ferragina,Grossi99]•etc,etc!Stateofthepractice:•B-trees+industrial-strengthfeaturesMichaelBender--PerformanceofFra
3、ctal-TreeDatabases2TheProblemProblem:maintainadynamicdictionaryondisk.Motivation:filesystems,databases,etc.Stateoftheart(algorithmicperspective):•B-tree[Bayer,McCreight72]•cache-obliviousB-tree[Bender,Demaine,Farach-Colton00]•buffertree[Arge95]•buffered-repositorytree[
4、Buchsbaum,Goldwasser,Venkatasubramanian,Westbrook00]•Bεtree[Brodal,Fagerberg03]•log-structuredmergetree[O'Neil,Cheng,Gawlick,O'Neil96]•stringB-tree[Ferragina,Grossi99]•etc,etc!Stateofthepractice:•B-trees+industrial-strengthfeaturesMichaelBender--PerformanceofFractal-T
5、reeDatabases3TheProblemProblem:maintainadynamicdictionaryondisk.Motivation:filesystems,databases,etc.Stateoftheart(algorithmicperspective):•B-tree[Bayer,McCreight72]•cache-obliviousB-tree[Bender,Demaine,Farach-Colton00]•buffertree[Arge95]•buffered-repositorytree[Buchsb
6、aum,Goldwasser,Venkatasubramanian,Westbrook00]•Bεtree[Brodal,Fagerberg03]•log-structuredmergetree[O'Neil,Cheng,Gawlick,O'Neil96]•stringB-tree[Ferragina,Grossi99]•etc,etc!Stateofthepractice:•B-trees+industrial-strengthfeatures/optimizationsMichaelBender--PerformanceofF
7、ractal-TreeDatabases4B-treesareFastatSequentialInsertsSequentialinsertsinB-treeshavenear-optimaldatalocalityMichaelBender--PerformanceofFractal-TreeDatabases5B-treesareFastatSequentialInsertsSequentialinsertsinB-treeshavenear-optimaldatalocalityTheseB-treenodesresideI
8、nsertionsareintoinmemorythisleafnode•OnediskI/Operleaf(whichcontainsmanyinserts).•SequentialdiskI/O.•Performanceisdisk-bandw
