Ed,

That was one place I looked yesterday. Section 6.2.4 which covers B-trees doesn't ever talk about it. There's a lot of discussion in the sections before about how a tree is kept balanced.

>Actually, Knuth talks about the insertion order problem for tree structures in some detail in volume 2 (Sorting and Searching, I think) but in a very theoretical context.