Fast way to find the number of files in one directory on Linux

Question

I am looking for a fast way to find the number of files in a directory on Linux.

Any solution that takes linear time in the number of files in the directory is NOT acceptable (e.g. "ls | wc -l" and similar things) because it would take a prohibitively long amount of time (there are tens or maybe hundreds of millions of files in the directory).

I'm sure the number of files in the directory must be stored as a simple number somewhere in the filesystem structure (inode perhaps?), as part of the data structure used to store the directory entries - how can I get to this number?

Edit: The filesystem is ext3. If there is no portable way of doing this, I am willing to do something specific to ext3.

Answer 1

Why should the data structure contain the number? A tree doesn't need to know its size in O(1), unless it's a requirement (and providing that, could require more locking and possibly a performance bottleneck)

By tree I don't mean including subdir contents, but files with -maxdepth 1 -- supposing they are not really stored as a list..

edit: ext2 stored them as a linked list.

modern ext3 implements hashed B-Trees

Having said that, /bin/ls does a lot more than counting, and actually scans all the inodes. Write your own C program or script using opendir() and readdir().

from here:

#include <stdio.h>
#include <sys/types.h>
#include <dirent.h>
int main()
{
        int count;
        struct DIR *d;
        if( (d = opendir(".")) != NULL)
        {
                for(count = 0;  readdir(d) != NULL; count++);
                closedir(d);
        }
        printf("\n %d", count);
        return 0;
}