Information contained in the block information is used for determining how to add the new key. The first entry in the table, the number of entries currently in the table, and the maximum number of entries that can fit in the table are saved in the block information. If the number of entries is less than the maximum number of entries, keys to the left of the new key are moved to the left, and the new key is inserted. To add a new key entry to a table that is already full, the table is split. When the split is made, all entries to the left of the new key and the new key go into one table, and all entries to the right go into another table. Inserting a Key and Inserting a Key into a Full Table show examples of inserting a key.

Example of Inserting a Key

Example of Inserting a Key into a Full Table