数据库管理系统概述英文版课件：10 B+tree

1、COMP231B+-treeCOMP2311OutlineB+-treeQueryUpdateInsertionDeletionCOMP2312Range SearchesFind all students with gpa 3.0If records are sorted on gpa, do binary search to find first such student, then scan to find others.Cost of binary search can be quite high.Simple idea: Create an “index” file.Page 1Pa

2、ge 2Page NPage 3Data Filek2kNk1Index FileCOMP2313B+ Tree: Most Widely Used IndexGeneral concept of a tree:rootleafLevel 1Level 3Level 4Internal nodeLevel 2Height of a node: its distance to the rootIf a higher level node is connected to a lower level node, then the higher level node is called a paren

3、t (grandparent, ancestor, etc.) of the lower level nodeCOMP2314B+ Tree (cont.)Balanced tree: all leaves at the same levelExample: Structure of a B+ tree:It is balanced: all leaf nodes are at the same levelEach node has a special structureCOMP2315Example: A B+ treeIn this example, each node holds at

4、least 1 entry, and at most 2 entriesGiven search key values 27, 64, how to find the rids? Search begins at the root, and key comparisons direct it to a leafNote that key values are sorted at each level10*15*20*27*33*37*40*46*51*55*63*97*2033516340RootAll keys = 40All keys 20Leaf nodeNon-leafnodeCOMP

5、2316B+ tree: Internal node structureP0 K1 P1 K2 Pi Pn-1 Kn PnEach Pi is a pointer to a child node, each Ki is a search key valuePointers outnumber search key values by exactly one.COMP2317Requirements:K1 K2 KnIf the node is not the root, we require d n 2d where d is a pre-determined value for this B

6、+ tree, called its orderIf the node is the root, we require 1 n 2d For any search key value K in the subtree pointed by Pi,If Pi = P0, we require that K K1If Pi = P1, , Pn-1, we require that Ki K Ki+1If Pi = Pn, we require Kn KCOMP2318B+ tree: leaf node structureL K1 r1 K2 Kn rn REach ri is a pointe

7、r to a record that contains search key value Ki L points to the left neighbor, and R points to the right neighbor K1 K2 = 24* .The last one is a range search, we need to do the sequential scan, starting from the first leaf containing a value = 24.Root1724302*3*5*7*14*16*19*20*22*24*27*29*33*34*38*39

8、*13=24*5*15*COMP23111Height/Depth of B+-treeWhat is the minimum height of the B+-tree?What is the maximum height of the B+-tree?COMP23112Minimum height of the B+-treeIn general nodes are pagesLet H be the height of the B+ tree: need to read H+1 pages to reach a leaf node Let F be the number of point

9、ers in a node (for internal node, called fanout ) Level 1 = 1 page = F0 pageLevel 2 = F pages = F1 pagesLevel 3 = Fx F pages = F2 pagesLevel H+1 = . = FH pages (i.e., leaf nodes)Suppose there are D data entries. So there are at least D/(F-1) leaf nodesD/(F-1) = logF( )12 levelHeight 0 1Note that dat

10、a entry is one less than pointersF = 2d+1COMP23113Maximum height of the B+-treeWhat is the maximum height of the B+-tree?COMP23114Cost of Searching a keyUsually, each node occupies a pageCost of searching a key = H + 1 (pages)COMP23115OutlineB+-treeQueryUpdateInsertionDeletionCOMP23116Inserting a Da

11、ta Entry into a B+ TreeFind correct leaf L. Put data entry onto L.If L has enough space, done!Else, must split L (into L and a new node L2)Redistribute entries evenly, put middle key in L2copy up middle key.Insert index entry pointing to L2 into parent of L.This can happen recursivelyTo split index

12、node, redistribute entries evenly, but push up middle key. (Contrast with leaf splits.)Splits “grow” tree; root split increases height. Tree growth: gets wider or one level taller at top.COMP23117Example 1: Inserting 16*, 8* into Example B+ treeRoot1724132*3*5*7*8*2*5*7*3*1724138*You overflow One mo

13、re child generated, must add one more pointer to its parent, thus one more key value as well. 14* 1516*COMP23118Example 1: Inserting 16*, 8* into Example B+ tree2*5*7*3*1724138*COMP23119Example 1: Inserting 16*, 8* into Example B+ tree2*5*7*3*1724138*2*3*5*7*8*5131724COMP23120Example 2: Inserting 16

14、*, 8* into Example B+ treeRoot172430132*3*5*7*8*2*5*7*3*172430138*You overflow One more child generated, must add one more pointer to its parent, thus one more key value as well. 14* 1516*COMP23121Example 2: Inserting 16*, 8* into Example B+ tree2*5*7*3*172430138*COMP23122Example 2: Inserting 16*, 8

15、* into Example B+ tree2*5*7*3*172430138*5131724302*3*5*7*8*You overflow COMP23123Example 2: Inserting 16*, 8* into Example B+ tree5131724302*3*5*7*8*COMP23124Example 2: Inserting 16*, 8* into Example B+ tree5131724302*3*5*7*8* 5 13 24 302*3*5*7*8*17COMP23125Example 2: Inserting 16*, 8* into Example

16、B+ tree 5 13 24 302*3*5*7*8*Root1717COMP23126Example 2: Inserting 16*, 8* into Example B+ tree 5 13 24 302*3*5*7*8*Root17COMP23127OutlineB+-treeQueryUpdateInsertionDeletionCOMP23128Deleting a Data Entry from a B+ TreeStart at root, find leaf L where entry belongs.Remove the entry.If L is at least ha

17、lf-full, done! If L has only d-1 entries,Try to re-distribute, borrowing from sibling (adjacent node with same parent as L).If re-distribution fails, merge L and sibling.If merge occurred, must delete entry (pointing to L or sibling) from parent of L.Merge could propagate to root, decreasing height.

18、COMP23129Ex1: Delete 19* and 20*2*3*Root17243014*16*19*20*22*24*27*29*33*34*38*39*1357*5*8* 22* 27* 29* 22* 24*UnderflowHave we still forgot something?40COMP23130Ex1: Delete 19* and 20*2*3*Root17273014*16*19*20*22*24*27*29*33*34*38*39*1357*5*8* 22* 27* 29* 22* 24*Underflow40COMP231312*3*Root173014*16*33*34*38*39*1357*5*8*22*24*2727*29*Ex2: Deleting 24*We cannot borrow from the sibling node.40COMP231322*3*Root173014*16*33*34*38*39*1357*5*8*22*2727*29*402*3*Root173014*