40
DISK-WRITE (x)
B-TREE-INSERT (T, k)
r
root[T]
if n[r] = 2t – 1
then
s
ALLOCATE-NODE()
root[T]
s
leaf[s]
FALSE
n[s]
0
c1[s]
r
B-TREE-SPLIT-CHILD (s, 1, r)
B-TREE-INSERT-NONFULL (s, k)
else
B-TREE-INSERT-NONFULL (r, k)
B-TREE-INSERT-NONFULL (x, k)
i
n[x]
if leaf[x]
then
while i = and k < key
i
[x]
do key
i+1
key
i
[x]
i
i – 1
key
i+1
[x]
k
n[x]
n[x] + 1
DISK-WRITE(x)
else while i = 1 and k < key
i
[x]
 |