bulk-loading. The first step is to sort the data entries according to a search key in ascending order. We allocate an empty page to serve as the root, and insert a pointer to the first page of entries into it. When the root is full, we split the root, and create a new root page. Keep inserting entries to the right most index page just above the leaf level, until all entries are indexed. Note : when the right-most index page above the leaf level fills up, it is split; this action may, in turn, cause a split of the right-most index page one step closer to the root; splits only occur on the right-most path from the root to the leaf level. Deletion The purpose of the delete algorithm is to remove the desired entry node from the tree structure. We recursively call the delete algorithm on the appropriate node until no node is found. For each function call, we traverse along, using the index to navigate until we find the node, remove it, and then work back up to the root. At entry L that we wish to remove: - If L is at least half-full, done - If L has only d-1 entries, try to re-distribute, borrowing from sibling (adjacent node with same parent as L). After the re-distribution of two sibling nodes happens, the parent node must be updated to reflect this change. The index key that points to the second sibling must take the smallest value of that node to be the index key. - If re-distribute fails, merge L and sibling. After merging, the parent node is updated by deleting the index key that point to the deleted entry. In other words, if merge occurred, must delete entry (pointing to L or sibling) from parent of L. Note: merge could propagate to root, which means decreasing height. Implementation The leaves (the bottom-most index blocks) of the B+ tree are often linked to one another in a linked list; this makes range queries or an (ordered) iteration through the blocks simpler and more efficient (though the aforementioned upper bound can be achieved even without this addition). This does not substantially increase space consumption or maintenance on the tree. This illustrates one of the significant advantages of a B+tree over a B-tree; in a B-tree, since not all keys are present in the leaves, such an