Editing B+ tree (section)

===Search===
We are looking for a value {{mvar|k}} in the B+ Tree. This means that starting from the root, we are looking for the leaf which may contain the value {{mvar|k}}. At each node, we figure out which internal node we should follow. An internal B+ Tree node has at most <math> m \le b </math>  children, where every one of them represents a different sub-interval. We select the corresponding child via a linear search of the {{mvar|m}} entries, then when we finally get to a leaf, we do a linear search of its {{mvar|n}} elements for the desired key. Because we only traverse one branch of all the children at each rung of the tree, we achieve <math>O(\log N)</math> runtime, where {{mvar|N}} is the total number of keys stored in the leaves of the B+ tree.<ref name=algorithms-pdf>{{cite web |url=https://www.cs.helsinki.fi/u/mluukkai/tirak2010/B-tree.pdf|title="B+ trees"|last=Pollari-Malmi|first=Kerttu|website=Computer Science, Faculty of Science, University of Helsinki|page=3|archive-url=https://web.archive.org/web/20210414050947/https://www.cs.helsinki.fi/u/mluukkai/tirak2010/B-tree.pdf|archive-date=2021-04-14}}</ref>

 '''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''' <math>|p| = |l| + 1</math>
     '''let''' m = p.len()
     '''for''' i '''from''' 1 '''to''' m - 1:
         '''if''' <math>k \le l[i]</math>:
             '''return''' leaf_search(k, p[i])
     '''return''' leaf_search(k, p[m])

Note that this [[pseudocode]] uses 1-based array indexing.