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

H. Peter Anvin (
28 Feb 1998 10:40:13 GMT

Followup to: <>
By author: Perry Harrington <>
In newsgroup:
> 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).


    PGP: 2047/2A960705 BA 03 D3 2C 14 A8 A8 BD  1E DF FE 69 EE 35 BD 74
    See for web page and full PGP public key
        I am Bahá'í -- ask me about it or see
   "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