Algorithms: Sequential, Parallel and Distributed 1-16
2.14 Suppose T is a B-tree of order m and depth d. Let ni denote the number of keys at depth i, i =
0, … , d, so that nd is the number of leaf nodes. Since each internal node having t keys has t + 1
21.15 Since the key k is assumed to be in an internal node, it follows that the child pointers to the
immediate left and to the immediate right of k both point to non-null children, which we call the left
and right children nodes of k, respectively. Moreover, the inorder predecessor of k is obtained by
21.16 Let α(m.d) denote the maximum number of keys contained in a B-tree of order m and
depth d. We then have
1
(2 1) 1
d
m
+
+−
21.17
Algorithms: Sequential, Parallel and Distributed 1-22
21.18
Algorithms: Sequential, Parallel and Distributed 1-23
Algorithms: Sequential, Parallel and Distributed 1-24
NOTE: In exercises 21.19-21.24, for simplicity we assume that all the keys in a B-tree are distinct.
It is straightforward to modify the algorithms to allow for duplicate keys.
21.19
Algorithms: Sequential, Parallel and Distributed 1-25
procedure B-TreeSearch(Root, k, Node, Index) recursive
Input: Root (→B-TreeNode) //pointer to the root of a B-tree T
k (a key)
21.20
procedure B-TreeNewRoot(Root, RChild, MedianKey)
Input: Root (→B-TreeNode) //pointer to the root of a B-tree T that will be Child[0] of new root
21.21
procedure NodeSearch(Root, k, Index)
Input: Root (→B-TreeNode) //pointer to the root of a B-tree T
21.22
procedure InsertKeyInNode(Node, k, m, Index, MedianKey, RChild)
Input: Node (→B-TreeNode) //pointer to node s of a B-tree T
k (a key to be inserted in T)
m (the order of T)
Node→Child[i + 1] ← Node→Child[i]
endfor
if RChild ≠ null then
Node→Child[Index + 1] ← RChild
endif
i ← i + 1
endwhile
//see if right child is full
if i < NumKeys – 1 .and. w→Child[i + 1]→NumKeys < 2*m then
//move key down from parent to right sibling
RightSibling→NumKeys ← RightSibling→NumKeys + 1
//move appropriate key in s up to parent and adjust
if Index = NumKeys then
//move k up
w→Key[i] ← k
if RChild ≠ null then
Node→Child[Index + 1] ← RChild
endif
Node→Key[Index] ← k
endif
if Index = 0 then
//move k up
w→Key[i – 1] ← k
//adjust pointers
LeftSibling→Child[NumKeys] ← Node→Child[0]
Node→Key[Index – 1] ← k
Node→Child[Index] ← RChild
endif
RChild ← null
return
//This key is either k, or Node→Key[m – 1] or Node→Key[m]
if Index = m then
//move k up to parent
MedianKey ← k
//Copy “2nd half” of s to node pointed to by Q
//Copy “2nd half” of s to node pointed to by Q
for i ← 0 to m – 1 do
Q→Key[i] ← Node→Key[i + m ]
Q→Child[i] ← Node→Child[i + m ]
endfor
MedianKey ← Node→Key[m]
//Copy “2nd half” of s to node pointed to by Q with k inserted
QIndex ← Index – m – 1
Algorithms: Sequential, Parallel and Distributed 1-29
for i ← 0 to QIndex – 1 do
if QIndex < m then
Q→Child[m] ← Node→Child[2* m]
endif
endif
endif