COW and volume management?
COW and volume management?
Posted Jan 27, 2026 15:07 UTC (Tue) by koverstreet (subscriber, #4296)In reply to: COW and volume management? by Wol
Parent article: Filesystem medley: EROFS, NTFS, and XFS
Hash tables are no-go in on disk data structures, they destroy locality and you can't do range lookups. Extents require range lookups, along with a lot of other things filesystems need to do, and we very frequently need to do efficient scans - btrees are much better suited to that.
Locality is a prime consideration when designing on disk data structures, and frequently you'll be doing short linear scans - linear searches are not slow as long as you keep them short.
E.g., the way bcachefs does full writeable snapshots, with versioning (so snapshots are at key granularity, not btree node granularity like btrfs) uses the low bits of the key as the snapshot ID - so a lookup finds either a key in the current snapshot, or an ancestor snapshot - that requires range lookups. But then for writeable snapshots, the snapshot ID is not a linear history, it's a tree; so we also have to skip over keys in unrelated branches of the snapshots tree. This search will be short for a variety of reasons (the main one being that creates always get a new inode number that won't be shared by any other snapshots), so snapshot lookups are fast; you can't do these kinds of tricks with hash tables.
