DEVEL15-windows-bplus-tree-20070823

DEVEL15-windows-bplus-tree-20070823

Windows uses case-insensitive file name pattern matching
but AFS is a case sensitive file system.  The AFS3 directory
format is block based, uses network byte order and
includes a hash table for fast case sensitive lookups.
This causes several problems for the Windows AFS client.
(1) Traversing the directory blocks is cpu expensive
(2) A hash table miss does not indicate that the desired
    entry does not exist.
(3) Determining whether a non-ambiguous inexact match or
    the entry does not exist requires a linear traversal
    of the entire directory.
These issues often result in 100% CPU utilization.

These issues are addressed by building a modified B+ tree for
each directory and then using the B+ tree for searches.

Further improvements can be made by using the B+ tree leaf
nodes for directory enumeration.

(cherry picked from commit c8bf408ced50cf9fba1595ec94368e4060223d89)