in the linked list. We can retrieve range retrieval or partial retrieval using B+ tree. This is made easier and faster by traversing the tree structure. This feature makes B+ tree structure applied in many search methods. Algorithms Search We are looking for a value in the B+ Tree. This means that starting from the root, we are looking for the leaf which may contain the value . At each node, we figure out which internal node we should follow. An internal B+ Tree node has at most children, where every one of them represents a different sub-interval. We select the corresponding child via a linear search of the entries, then when we finally get to a leaf, we do a linear search of its elements for the desired key. Because we only traverse one branch of all the children at each rung of the tree, we achieve runtime, where is the total number of keys stored in the leaves of the B+ tree. function search(k, root) is let leaf = leaf_search(k, root) for leaf_key in leaf.keys(): if k = leaf_key: return true return false function leaf_search(k, node) is if node is a leaf: return node let p = node.children() let l = node.left_sided_intervals() assert let m = p.len() for i from 1 to m - 1: if : return leaf_search(k, p[i]) return leaf_search(k, p[m]) Note that this pseudocode uses 1-based array indexing. Insertion Perform a search to determine what bucket the new record should go into. If the bucket is not full (at most entries after the insertion), add the record. Otherwise, before inserting the new record split the bucket. original node has ⎡(L+1)/2⎤ items new node has ⎣(L+1)/2⎦ items Copy ⎡(L+1)/2⎤-th key to the parent, and insert the new node to the parent. Repeat until a parent is found that need not split. Insert the new record into the new node. If the root splits, treat it as if it has an empty parent and split as outline above. B-trees grow at the root and not at the leaves. Bulk-loading Given a collection of data records, we want to create a B+ tree index on some key field. One approach is to insert each record into an empty tree. However, it is quite expensive, because each entry requires us to start from the root and go down to the appropriate leaf page. An efficient alternative is to use