Steve Dirickson b894 WestWin wrote:
>
> OK, I'll ask the stupid question: why should a severely unbalanced B-Tree
> impact the ability of the structure to hold the data? Obviously,
> performance of the B-Tree will go down the tube as it becomes, in
> essence, a very expensive linear search to put something into or get
> something out of the list. But I can't think of anything that would cause
> the structure to become somehow unable to simply *hold* the information,
> no matter how severely unbalanced; a node is a node, independently of
> whether it is 50 levels deep in a balanced tree or 500,000 "levels" down
> in a "linear tree". Now MPE might get "tired" as it searched this
> ever-longer list trying to figure out where to put the data, but that
> would seem to be pretty unlikely. So what are we talking about as the
> limiting factor? Directory-block allocation granularity? Device timeouts
> waiting for MPE to decide where to put the directory entry? Running out
> of disk space to hold the partially-full nodes? What am I missing?
>
I do not remember all the details, but I think the limitation was/is
in the alghorithm rather than in the data structures. There is a limited
amount of 'notes' for a 'block' of file entries (ca. 40 per block ??)
and
the algorithm can only 'shuffle' an entry into the next neighbouring
node/block. Shuffling into second next, or recursive shuffling was not
implemented because of performance contraints (?).
Practical worst case is at about 117 files (?), theoretical limit
(with 'nice' filenames and filling order) is around 11xx files.

That is what memory serves at the moment...

Goetz (normally @hp.com)