Tree structures lend themselves to external searching, if we choose an appropriate representation for grouped nodes. From Knuth volume 3, section 6.2.4.
See test in javascript. page 
The b-tree, discovered in 1970, makes both search and update guaranteed efficient. A b-tree of order m satisfies these properties.
* Every node has at most m children. * Every interior node has at least m/2 children. * The root has at least 2 children, unless it is a leaf. * All leaves appear on the same level, carry no info. * A nonleaf node with k children has k-1 keys.
A node p with j keys will have j+1 pointers.
p0, k1, p1, k2, p2 ... pj-1, kj, pj
Search: if p does not contain k, search non-null pi where k is between ki and ki+1.
Insert: if p is full, split and update p's parent. Add a level when root splits.
Delete: left as exercise 6.
The b+-tree varies k with node level, omits records from interior nodes and links each leaf to its successor for sequential access.
The b*-tree delays splits by moving keys to siblings. When sibling fills, we split two nodes into three, each 2/3 full.
Search Index requires log behavior typically provided by b-tree variations so as to not break in large neighborhoods.