B+Tree INSERTION ALGORITHM: Rewrite by ad-at+di.uoa.gr ** B+ Nodes maintain n-1 key values and n pointers 1. Find the leaf page in which the insertion should take place. 2. If there is space, put the new key in, rearrange keys and exit. 3. If there is no space for the newly arrived key, then allocate a new leaf node. Split the keys between the two nodes. ceil(n/2) keys/values go into the 1st block and the remaining into the 2nd. Propagate upwards the first key/value of the 2nd block. 4. If insertion in the internal node is possible then do the insertion (of the just propagated key), re-arrange pointers properly, and exit. Otherwise, The internal node has to be split up: - Acquire a new block. - All the keys less than the MEDIAN go to the 1st block and all the keys greater than the median go to the 2nd (WITHOUT the median). - Rearrange and keep track of pointers properly. - The median needs to be up-propagated Goto to 4.