- VEB(i):
- if i is a constant:
- store a list of keys-record pairs
- otherwise:
- keep records with min and max keys separate
- in instance variables top,bottom
- partition remaining records into subsets Si
- record with key x goes into Si( hi(x) )
- for each non-empty subset Si:
- create recursive data structure VEB(i/2) “Li”
- stores records of Si but where every record
- only uses the low half of its keys: lo(x)
- store dictionary D
- D(i) maps instance i to Li
- create recursive data structure VEB(i/2), called H
- success(q)
- if D[hi(q)] is nonempty:
- if lo(q) ⇐ D[hi(q)]'s top key:
- We have a nonempty recursive structure with the same high half
- with at least one element which could be >= q
- return D[hi(q)].success(lo(q))
- try:
- return H.successor(hi(q)+1).bottom
- except:
- return top
- insert(object x, key k):
- if 0 items already:
- top = x
- bottom = x
- if 1 item already:
- update top or bottom to x
- if more than 1 item:
- check for updating top and bottom
- if D[hi(k)] nonempty:
- store x,lo(k) in D[hi(k)]
- else:
- make new VEB(i/2) L for …
- …
- …
- deletion is a little more complicated.
- If it is the top or bottom,
- the new top or bottom has to be found and removed

=== Fusion Tree ===

Time bound depends only on n, the number of items in the structure.

Fusion tree is a [http://en.wikipedia.org/wiki/B-Tree B-tree] with B = , but each node is stored as a compressed trie of its keys as binary number. Plus clever binary table-lookup tricks and arithmetic to make it fast.

B-tree: balanced search tree with greater than 2 children per node. The number of children is between B and 2B. Its height is .

- * O(log n / log B) steps to search
- each step may use O(log B) to find the correct child
- * update is also slow
- each step may use O(B) time
- * search or update uses only O(log n / log B) block I/O operations

Each node contains a number of keys within a set range. For keys within the node, there will be child references to sub-trees defined by the values of the keys.