一些树的结构备忘NULL 博文链接：https://richyzhang.iteye.com/blo

文件名称: 一些树的结构备忘

所属分类: 其它

开发工具:

文件大小: 288kb

下载次数: 0

上传时间: 2019-07-29

提供者: weixin_********

下载 (288kb)

不能下载？报告错误

详细说明：NULL 博文链接：https://richyzhang.iteye.com/blog/803019B+ Trees http://babbage.clarku.edu!achou/cs160/b+trees/b+trees.htm Add record with Key 28 2515075 51015202528305055606575808590 Adding a record when the leaf page is full but the index page is not Next, we're going to insert a record with a key value of 70 into our B+ tree. This record should go in the leaf page containing 50, 55, 60, and 65. Unfortunately this page is full. This means that we must split the page as follows Left Leaf Page Right Leaf Page 606570 The middle key of 60 is placed in the index page between 50 and 75 The following table shows the b+ tree after the addition of 70 Add record with Key 70 2550607 51052012528305055 606570 7580|8590 Adding a record when both the leaf page and the index page are full As our last example, we're going to add a record containing a key valuc of 95 to our b+ trec. This record belongs in the page containing 75, 80, 85, and 90. Since this page is full we split it into two pages Left Leaf Page Right Leaf Page 3 of 8 1/20054:10AM B+ Trees http://babbage.clarku.edu/achou/cs160/b+trees/b+trees.htm 7580 859095 The middle key, 85, rises to the index page. Unfortunately, the index page is also full, so we split the index page Left Index Page Right Index Page New Index Page 2550 7585 The following table illustrates the addition of the record containing 95 to the B+ tree Add record with Key 95 50四 510152025282305055006570 75|80 859095 Rotation B+ trees can incorporate rotation to reduce the number of page splits. a rotation occurs when a leaf page is full, but one of its sibling pages is not full. Rather than splitting the leaf page, we move a record to its sibling, adjusting the indices as necessary. Typically, the left sibling iS checked first(if it exists )and then the right sibling As an example, consider the b+ tree before the addition of the record containing a key of 70. As previously stated this record belongs in the leaf node containing 50 60 65. Notice that this node is full, but its left sibling is not 4 of 8 1/20054:10AM B+ Trees http://babbage.clarku.edu/achou/cs160/b+trees/b+trees.htm Add record with Key 28 2515075 51015202528305055606575808590 Using rotation we shift the record with the lowest key to its sibling. Since this key appeared in the index page we also modify the index page The new b+ tree appears in the following table Illustration of rotation 255575 510152025283050|55606505808590 Deleting Keys from a B+tree We must consider three scenarios when we delete a record from a bt tree. each scenario causes a different action in the delete algorithm. The scenarios are 5 of 8 11/1/20054:10△M B+ Trees http:/babbage.clarku.edu/achou/cs160/b+trees/b+trees.htm The delete algorithm for B+ Trees Leaf Page Index page Below fill Below fill action factor Factor Delete the record from the leaf page. arrange keys in ascending order NO NO to fill void. If the key of the deleted record appears in the index page use the next key to replace it YES NO Combine the leaf page and its sibling. Change the index page to flect the change 1. Combine the leaf page and its sibling 3. Combine the index page with its sibling 2. Adjust the index page to reflect the change YES YES Continue combining index pages until you reach a page with the correct fill factor or you reach the root page As our example, we consider the b+ tree after we added 95 as a key as a refresher this tree is printed in the following table Add record with key 95 2SN50■ 7585 5101520252830 5055 606570 75|80 859095 Delete 70 from the b+ tree We begin by deleting the record with key 70 from the b+ tree. This record is in a leaf page containing 60, 65 and 70. This page will contain 2 records after the deletion Since our fill factor is 50% or(2 records )we simply delete 70 from the leaf node. The following table shows the b+ tree after the deletion of 8 11/1/20054:10△M B+ Trees http://babbage.clarku.edu/achou/cs160/b+trees/b+trees.htm Delete Record with Key 70 60工 250 75H85 51015202528305055606 7580 859095 Delete 25 from the bt tree Next, we delete the record containing 25 from the B+ tree. This record is found in the leaf node containing 25, 28, and 30. The fill factor will be 50% after the deletion; however, 25 appears in the index page. Thus, when we delete 25 we must replace it with 28 in the index page The following table shows the bt tree after this deletion Delete Record with Key 25 60N 刚507585 5101520283050556065 7580 859095 7 of 8 1/20054:10AM B+ Trees http://babbage.clarku.edu/achou/cs160/b+trees/b+trees.htm Delete 60 from the bt tree As our last example, we're going to delete 60 from the B+ tree. This deletion is interesting for several reasons 1. The leaf page containing 60(60 65)will be below the fill factor after the deletion. Thus, we must combine leaf pages 2. With recombined pages, the index page will be reduced by one key. Hence, it will also fall below the fill factor Thus, we must combine index pages 3. Sixty appears as the only key in the root index page. Obviously, it will be removed with the deletion The following table shows the b+ tree after the deletion of 60. notice that the tree contains a single index age Delete record with Key 60 28507585 510152028|30 505565 7580 859095 Copyright, 1998, Susan Anderson-Freed 8 of 8 1/20054:10AM

(系统自动生成,下载前可以参看下载内容)