Re: A request to those people who want B-tree directories

H. Peter Anvin (hpa@transmeta.com)
28 Feb 1998 10:40:13 GMT

Followup to: <199802271755.JAA03421@sun4.apsoft.com>
By author: Perry Harrington <pedward@sun4.apsoft.com>
In newsgroup: linux.dev.kernel
>
> One thing to consider when you do a btree: creation of btrees is
> expensive, if most of your data is transient in a directory, btrees
> don't help performance, neither if you're just doing linear dumps of
> a directory. Btrees only help in the name->number conversion, if
> you are processing a directory in linear order they will slow things
> down.
>

Yes, a sequential dump of a directory is a lost cause -- it is O(n) no
matter what you do. Having a tree structure reduces the order of a
lookup from O(n) to O(log n).

-hpa

-- 
    PGP: 2047/2A960705 BA 03 D3 2C 14 A8 A8 BD  1E DF FE 69 EE 35 BD 74
    See http://www.zytor.com/~hpa/ for web page and full PGP public key
        I am Bahá'í -- ask me about it or see http://www.bahai.org/
   "To love another person is to see the face of God." -- Les Misérables


-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu