Don't walk the tree: how NTFS file search really gets fast

If you asked most developers to build "find every file matching X on this drive," the instinct is some version of: open a directory, list its entries, recurse into the subdirectories, repeat. That works, and for a few thousand files it's instant. Point it at a real Windows machine with millions of files across several drives and it turns into a slideshow.

The reason isn't your code. It's the access pattern.

Walking the tree is death by a thousand syscalls

Every directory you descend into is at least one system call, often several, and on a spinning disk each one can be a seek. The cost scales with how many directories you have, and the work is mostly waiting: the CPU sits idle while the OS fetches one small directory listing after another. You aren't bottlenecked on matching filenames, you're bottlenecked on the shape of the traversal itself.

NTFS already built the index for you

Here's the thing the tree-walk approach ignores: NTFS already keeps a complete catalog of every file and directory on the volume. It's called the Master File Table (MFT), and it's essentially one big array of fixed-size records, one record per file or directory. Each record holds the name, a reference to the parent directory, the size, the timestamps, and the rest of the metadata.

So instead of walking the tree one folder at a time, you can read the MFT directly: one large, mostly sequential read of a structure the filesystem maintains for you anyway. Then you do your matching in memory, over that array.

The difference in shape is the whole point. The left side is hundreds of thousands of small, latency-bound requests. The right side is one big streaming read plus an in-memory scan. Same result, completely different performance envelope.

The catches (because there are always catches)

This isn't free, and it's worth being honest about the tradeoffs:

• It's NTFS-specific. This is a Windows and NTFS trick, not a portable filesystem API.
• The MFT doesn't store full paths. Each record only knows its own name and its parent's record number. To print C:\Users\you\report.pdf you have to walk the parent chain back up and stitch the path together yourself. (Interning the directory names helps a lot, since the same folders show up over and over.)
• Reading the raw MFT needs elevated access to the volume, because you're going underneath the normal file APIs and reading the device directly.
• You're now parsing an on-disk binary format, with all the edge cases that implies: extension records, hard links, unusual names.

None of these are dealbreakers, but they're the reason "just read the MFT" is a sentence that hides a fair amount of work.

Why I went down this road

This is the core idea behind a file search engine I've been building in Rust. Once you stop thinking of search as "traverse the filesystem" and start thinking of it as "load the index the filesystem already has, then query it," a lot of other decisions (caching, a resident daemon, in-memory querying) fall out of that one shift.

The broader lesson has nothing to do with Windows: when something feels slow, look at the access pattern before you optimize the work. The tree walk and the MFT read do the exact same logical job. One is just shaped like something the hardware is good at.

I'm building this as UltraFastFileSearch (UFFS), a Rust NTFS search engine. The code is on GitHub, there's a benchmark writeup with the raw logs, and demos on YouTube.