PHYSICAL DATABASE DESIGN - Fundamentals of Database Management Systems - page 214

The final point to make about B + -tree indexes is that, unlike simple linear
indexes, they are designed to comfortably handle the insertion of new records into
the file and the deletion of records. The principle for this is based on the idea of unit
splits and contractions, both at the record storage level and at the index tree level.
For example, say that a new record with salesperson number 365 must be inserted.
Starting from the root and following the same procedure for a record search, the
computer determines that this record should be located on Cylinder 5 in order to
maintain the sequence of the records based on the salesperson number key. If there
is room on the track on the cylinder that it should go into to maintain the sequence,
the other records can be shifted over and there is no problem. If the track it should
go into is full but another track on the cylinder has been left empty as a reserve,
then the set of records on the full track plus the one for 365 can be ''split,'' with
half of them staying on the original track and the other half moving to the reserve
track. There would also have to be a mechanism to maintain the proper sequence of
tracks within the cylinder, as the split may have thrown it off.
But suppose that cylinder 5 is completely full. Then the collection of records
on the entire cylinder has to be split between cylinder 5 and an empty reserve
cylinder, say cylinder 11, Figure 8.16. That's fine, except that the key value of 368
in the tree index's lowest level still points to cylinder 5 while the record with key
value 368 is now on cylinder 11. Furthermore, there is no key value/pointer pair
representing cylinder 11 in the tree index, at all! If the lowest-level index record
containing key value 368 had room, a pointer to the new cylinder could be added and
the keys in the key value/pointer pairs adjusted. But, as can be seen in Figure 8.14,
there is no room in that index record.
Figure 8.17 shows how this situation is handled. The index record into which
the key for the new cylinder should go (the middle of the three index records at
the lower level), which happens to be full, is split into two index records. The
now five instead of four key values and their associated pointers are divided, as
equally as possible, between them. But, in Figure 8.14, there were three key values
in the record at the next level up (which happens to be the root), and now there
are four index records instead of the previous three at the lower level. As shown in
Figure 8.17, the empty space in the root index record is used to accommodate the
new fourth index record at the lower level. What would have happened if the root
index record had already been full? It would have been split in half and a new root
at the next level up would have been created, expanding the index tree from two
levels of index records to three levels.

Records
with
Salesperson
Numbers
310-330 Records

with
Salesperson
Numbers
332-368

F I G U R E 8.16
The records of cylinder 5 plus the
newly added record, divided between
cylinder 5 and an empty reserve cylinder,
cylinder 11

Cylinder 5

Cylinder 11