Muq btrees are a fairly stock implementation, except that nonleafl key comparisons are done on hashes of the key values rather than the key values directly, which may speed access in some cases, such as perhaps when the keys are long strings with a common prefix.
Currently, internal nodes contain about 10-20 children, with leaf nodes containing about 7-15 key-val pairs: Searching is linear within both kinds of nodes. (Linear unsorted lists are usually the fastest algorithm for list lengths less than about 8-16.)
This means that for very small btrees, insertion and deletion performance is close to that of unsorted lists, typically requiring no storage allocation or garbage collection, while for very large btrees, efficiency is close to that usually achieved in databases: A btree with a million entries will be only three levels deep.
Go to the first, previous, next, last section, table of contents.