资源描述：
《由两个level所组成.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、B+TreedefinitionB+treeoforderm由兩個level所組成：Indexlevel及Datalevel所組成所有Data均存在於DataBlocksonDataLevel,DataBlocks之間以Linklist串連IndexBlock主要是依據key,配合索引,找到對應的DataBlock而IndexBlock及DataBlock中的Degree數必須符合Btreeoforderm的規定B+Tree(balancedTree)：所有樹葉到樹根的距離都相同 每個節點有+m/2T～ｍ個子女（樹根除外） 所有樹葉都在同一層（樹根到樹葉的深度皆
2、相同） 具有n個子女非樹葉節點有n-1個鍵可以supportISAM(IndexSequentialAccessMethod),主要用在externalsearch,SORT上例：B與B+tree的比較B+_tree在定義上與B_tree不同，圖2畫出一個B+_Tree的例子，在B+_Tree中，只有葉節點的索引記錄才含有資料指標，其餘的節點中僅含有單純的索引值，請注意圖1中B_tree的情況是與此不同的。為何要有B+_Tree呢?由於B+_Tree的內節點（Internalnode）不含資料指標，每個節點能存放的索引數目會比較多，相對地樹狀結構的層級數目就少一
3、點，減少了資料方塊存取的數目，所以在實際的應用上，仍以B+_Tree較為多見。6,97,81,410,1386,71,49810,1369,10圖2圖1CreataB+tree插入的順序為:9,6,1,8,4,13,10,76,9166,916,868,91,46,868,9861,49,1386986,71,49810,1369,10861,49810,1369,10InsertakeyInsertakeyintoaleafwhichstillhassomeroom(notoverflow).Putthekeysofthisleafinorder.Nochan
4、gesaremadeintheindexlevel.166,91,466,9insert4Ifakeyisinsertedintoafullleaf(overflow)Split,thenewleafnodeisincludedinthesequenceset,keysaredistributedevenlybetweentheoldandthenewleaves,andthefirstkeyfromthenewnodeiscopied(notmoved,asinB-tree)1,466,91,46,96TheparentisnotfullTheparentis
5、fullInsert109,10Insert31369,103,466,9DeleteakeyDeleteakeyfromaleafleadingtonounderflowDeletetheleafandkeepremainingkeysinorderindexlevel可刪可不刪delete41,46,969,1016,969,10delete91,46,106101,46,9610DeleteakeyfromaleafcausesanunderflowRotationorCombination1363,466,99,10delete146466,99,103
6、delete613,46,99,10EX:B+Treeoforder3.(a)Initialtree608020,40205,106040,5080,100IndexlevelDatalevel6020,40205,106040,508080,100100,120(b)Insert“120”608020,40205,106040,5080,100,120Overflow(c)Insert“150”6020,40205,106040,508080,100100,120,150Overflow20,40205,106040,5080120,1508060,10012
7、0100(c)Delete“40”20,40205,106040,5080120,1508060,10012010020,50205,10605080120,1508060,100120100(c)Delete“100”20,40205,106040,5080120,1508060,10012010020,50205,106050801508060,120150120Underflowrotation(c)Delete“150”20,50205,106050801508060,12015012020,50205,106050806012080,120
