Indexing a million files on a laptop

A normal laptop holds somewhere between a few hundred thousand and a few million files once you count caches, photo libraries, source checkouts and node_modules folders. Indexing a million files so you can find any of them by name in the time it takes to type is a well understood problem, but the details are easy to get wrong. This is how we think about it.

This post is not a description of any one product. It is the general shape of the problem and the trade-offs any local file index has to make, written down the way we would explain it to someone joining the project.

Four stages

Every file index we know of, from the ones built into operating systems to small open-source tools, is some version of the same pipeline:

Walk. Read every directory once to build the first picture of the disk.
Events. Ask the operating system to tell you when things change, so you never have to walk everything again.
Index. Store names and a little metadata in a structure built for searching.
Query. Turn a few typed letters into a ranked list, without touching the disk tree at all.

The walk is slow and rare. Events are small and constant. Queries have to be instant. Most design mistakes come from mixing those up, for example re-walking a folder on every search, or doing expensive work inside the event handler.

Walking the disk

The first walk is the part users notice, because it is the only part that takes a visible amount of time. The basic loop is simple: open a directory, list its entries, get size and modification time for each, recurse into subdirectories. The cost is almost entirely system calls and disk metadata reads, not your own code.

A few things make a large difference.

Use the bulk APIs. Calling stat separately on every file is the slow way. On macOS, getattrlistbulk returns names and attributes for many entries in one call. On Windows, FindFirstFileEx with the large-fetch flag returns size and timestamps along with each name. On NTFS there is a much faster trick: with administrator rights you can enumerate the Master File Table directly through the USN journal APIs (FSCTL_ENUM_USN_DATA) and get every file record on the volume without walking directories at all. Tools that index a whole NTFS drive in seconds are usually doing this.

Walk in parallel, but not too much. On an SSD a handful of worker threads walking different subtrees helps. On a spinning disk or a USB stick it can make things slower, because the drive ends up seeking between them. We would rather detect the kind of volume and choose than pick one number for everyone.

Skip what nobody searches for. System folders, package caches, .git object directories and build output can easily be half of all files on a developer's machine. Sensible default skip rules, visible and editable, make the index smaller and the results better.

Be careful with links. Symbolic links and junctions can create cycles. Track the device and inode (or file ID on Windows) of every directory you enter, and do not enter one twice.

How long does a walk of a million files take? It depends heavily on the filesystem, the drive and how much metadata is already cached in memory. On a recent laptop SSD it is usually in the range of tens of seconds to a few minutes. The second time is often much faster because the operating system has cached the directory data. If a design only works when the walk is fast, it will fail the first time someone plugs in a slow external drive.

Change notifications on each platform

After the first walk, the index should stay current without walking again. Each operating system offers a different mechanism, and they have different failure modes.

macOS: FSEvents

FSEvents reports changes for a whole directory tree with a single subscription. By default it tells you which directories changed rather than which files, and you rescan those directories. With the file-events flag it reports individual files. The useful property is that FSEvents keeps a persistent log per volume. Each event has an ID, and when your app starts it can ask for everything since the last ID it saw. That means changes made while the app was closed are not lost, which is exactly what an indexer needs. The log can still be reset or incomplete, and the API tells you when you need to rescan, so you must handle that case.

Windows: ReadDirectoryChangesW and the USN journal

ReadDirectoryChangesW watches a directory tree and reports file-level changes. It is easy to use, but if changes arrive faster than you read them, the buffer overflows and you are told only that you missed something. On NTFS the USN change journal is more dependable: the filesystem records every change in a journal with a sequence number, and you can read from where you left off, even after a reboot. The journal has a fixed size and old entries wrap around, so if your app was away for a long time on a busy disk, you may still need a partial rescan.

Linux: inotify and fanotify

inotify is not recursive. You need one watch per directory, and the number of watches per user is limited by fs.inotify.max_user_watches. Older kernels defaulted to 8,192, which is far too low for a home directory. Newer kernels scale the default with memory, but it is still worth checking. fanotify can watch a whole filesystem and, on recent kernels, report which file changed, but it needs elevated privileges. Neither keeps history while your process is not running, so a Linux indexer has to reconcile on startup, usually by comparing directory modification times.

The common rule across all three: treat events as hints, not truth. When an event arrives, re-read the metadata for the path it names and update the index from what is actually on disk. Events can be coalesced, reordered or dropped, and a rename is often reported as two separate changes.

What to store, and how much memory it costs

The naive design stores the full path of every file as a string. With an average path of around 100 bytes, a million files is about 100 MB of path text before any index structures. That is too much for something that runs in the background all day.

The usual fix is to store the tree, not the paths. Each record holds a numeric ID, its parent's ID, the file name, size, modification time and a few flags. Names are short, typically 15 to 30 bytes, and full paths are rebuilt only for the results you actually display. That alone can cut the memory for names by a factor of four or five.

What you leave out matters as much. A filename index does not need file contents, thumbnails or hashes. Content search is a much larger problem with a much larger index, and mixing the two tends to make the filename search slower. If we want contents or hashes, we would add them as a separate, optional layer.

Searching: prefixes, trigrams and SQLite FTS5

People do not search for the start of a file name. They type "invoice" and expect to find "2025-03-invoice-final.pdf". That rules out a simple sorted list with prefix search, which only finds matches at the start of a name.

Trigram indexes are the standard answer. Every name is broken into overlapping three-character pieces, and each piece points to the names that contain it. A search for "invoice" becomes a lookup of "inv", "nvo", "voi", "oic" and "ice", an intersection of those lists, and a final check of the few names that survive. It handles matches anywhere in the name and stays fast at millions of entries.

You do not have to write one. SQLite's FTS5 extension has had a trigram tokenizer since version 3.34, and it can answer LIKE '%invoice%' style queries using the index:

CREATE VIRTUAL TABLE names USING fts5(
  name, content='files', content_rowid='id',
  tokenize='trigram case_sensitive 0'
);

SELECT id FROM names WHERE name MATCH 'invoice' LIMIT 200;

SQLite also gives you transactions, which matter when a burst of events arrives. Batch updates into one transaction every second or so rather than one per event, and the index stays consistent if the app is killed halfway through. Two limits to know about: trigram search needs at least three characters, so one and two-letter queries need a separate path, and the index adds real size on disk, often more than the table it indexes.

Ranking is where a tool develops a personality. Exact name matches first, then matches at the start of a word, then recent files, then everything else is a reasonable default. It is also something users notice more than raw speed once searches are under about 50 milliseconds.

External drives and other awkward cases

External drives are the case that separates careful indexers from simple ones. A drive can disappear mid-walk. It can come back with a different mount point or drive letter. It can be formatted with exFAT, which has no change journal, so changes made on another computer are invisible until you rescan. Network shares are worse: change notifications over SMB are unreliable, and walking a large share can be very slow.

The approach we like is to identify volumes by their filesystem UUID or serial number rather than their path, keep each volume's index separate, and mark a volume as offline rather than deleting its entries when it is unplugged. Searching an unplugged drive's index is useful. You can at least find out which drive the file is on.

If you are building something like this for your own product, it is the kind of work we do in custom development projects too. The best first step is not code. Count the files on the machines of five real users, including their external drives, and write the numbers down. Every decision above gets easier once you know if the real number is two hundred thousand files or eight million.