Re: [rfc] Near-constant time directory index for Ext2

[H. Peter Anvin]

Mark Hahn wrote:
> 
> > You're right.  However, for each hash table operation to be O(1) the size
> > of the hash table must be >> n.
> 
> there's at least one kind of HT where the table starts small
> and gets bigger, but at trivial cost (memcpy).  while those
> memcpy's are O(n) each time, it's a little misleading to treat
> them as costing the same as O(n) rehashing.
> 

memcpy() isn't exactly trivial, especially not when we're talking about
disk storage.  Note, too, that we're talking about storage in a
filesystem, and random access a large, growable linear space (i.e. a
file) in a filesystem is O(log n) because of necessary inode indirection.

That's yet another reason I like the idea of using B-trees over hash
values: B-trees are O(log n), but do not need the file inode indirection
to do the job, so what you end up with is very nice and fast.

	-hpa

-- 
<[e-mail]> at work, <[e-mail]> in private!
"Unix gives you enough rope to shoot yourself in the foot."
http://www.zytor.com/~hpa/puzzle.txt