b_book1.gif (162 bytes)Data - Structures (Tree)

B+-tree: Adding/Inserting records (1 of 2)
STOCK file:
The records arrive in the order shown below.
Record No StockID Description Qty ReOrderAt Price
1 1035 90W stereo 2 1 $2000.00
2 2015 Video - nicam 4 2 $799.00
3 1069 24" TV 3 1 $995.00
4 3010 Walkman 5 4 $250.00
5 1020 ABC Speakers 3 2 $500.00
6 1045 CD cleaner 10 5 $22.00
7 2010 Video 2 3 $675.00
8 2950 80W stereo 4 1 $1500.00
9 1041 Headphones 4 2 $10.00
10 1278 29" TV 5 2 $1200.00
  • A B+-tree with a bucket factor (Bktfr) = 4 (also called the degree) is created.
  • The first four records are added to the root of the B+-tree.

dadstra1.gif (8238 bytes)
  • Stock number "1020" is added. The number of keys in the root is 5 and exceeds the Bktfr (4) so the root is split. (2:3).
    The smallest key in the Right hand side (RHS) "1069" becomes the new parent.
  • "1045" needs to be added.
    The tree is searched for the record by labeling the pointers 0..4, The key "1045" is smaller than the first key "1069", so pointer 0 followed. The pointers are followed "1020","1035" and room is found in the leaf so the key value "1045" is added.
  • "2010" is added.
 dadstra2.gif (14325 bytes)

[Rev 13/03/99] 12/3/99 © 1999 V/2-Com (Verhaart), P O Box 8415, Havelock North, New Zealand.