Example of Multi-level trees

a

b c

d e f g

h i j k l m n o

In the complete binary tree above, with BF = 3, the blocks in the level-order case would be (abc)(def)(ghi)(jkl)(mno) and three accesses on most paths. (For example, searching for k has to look at blocks (abc), (def), and (jkl).

For the multi-level tree with k=2 illustrated below, we would have (abc)(dhi)(ejk)(flm)(gno), and two accesses.

a

b c

d e f g

h i j k l m n o