A database file presents one logical byte sequence:

The storage underneath does not have to contain one continuous 10 GiB region reserved from the beginning. The file may grow over time, occupy several separated runs, and contain logical gaps that consume no data blocks.

The file system is responsible for connecting the two views:

This responsibility is file allocation.

File allocation decides which file-system blocks represent each allocated part of a file and records the mapping from logical offsets to those blocks.

Modern file systems commonly describe contiguous runs with extents. One extent can map many logical blocks with a compact (logical start, storage start, length) record.

The word block is used at several layers, so the unit must be stated explicitly.

A device sector is an addressable unit exposed by a storage device or block-device interface. A file-system block is the allocation and mapping unit chosen by the file system. An application record is a unit defined by software such as a database.

The sizes can differ. One 16 KiB database page can occupy four 4 KiB file-system blocks. Each file-system block can cover several device sectors.

st_blksize reported by stat() is commonly a preferred I/O size for the file, not a reliable statement of either the physical sector size or the actual allocation unit. On Linux, st_blocks reports allocated space in 512-byte accounting units.

In this chapter, logical block means a block-sized position within one file. Storage block means a block address in the file system's lower-level allocation view.

Even “storage block” is not necessarily a literal flash or platter location. RAID, volume management, SSD controllers, and other lower layers can remap it again.

Suppose the file system uses 4 KiB blocks and an application reads byte offset 70,000.

First find the logical file block:

Then find the position inside that logical block:

The file's allocation metadata must answer:

Assume an extent says:

It maps:

Logical block 17 is one block after the extent's logical start, so it maps to storage block 7,001. The requested byte is 368 bytes into that storage block.

An extent lookup turns the logical position, file block 17 byte 368, into the storage position, storage block 7,001 byte 368.

Applications use the logical offset. The file-system implementation performs this mapping.

An allocation design balances several goals.

It should support efficient sequential access and reasonable random access. It should let files grow without requiring their final size in advance. Its mapping metadata should remain compact. It should find free space quickly under concurrent workloads and avoid turning every growing file into thousands of tiny fragments.

These goals can conflict:

Allocation is therefore policy as well as representation. The representation says how mappings are recorded. The policy chooses which currently free blocks to use.

The simplest representation gives a file one continuous storage run:

Logical block L maps with:

This is compact and fast. Sequential access follows adjacent blocks, and random access needs only arithmetic.

The problem is growth. If the next storage block belongs to another file, extending the run requires moving the file, finding another large region, or adding a second run.

As files are created, expanded, and removed, free capacity can become divided into small ranges. A file system may have enough total free blocks but no one free run large enough for a requested contiguous allocation.

Pure one-run contiguous allocation is therefore poorly suited to arbitrary long-lived, growing files. Extent-based allocation keeps its useful idea, representing contiguous runs compactly, without requiring every file to remain one run.

In linked allocation, each data block identifies the next data block:

Each block stores the location of the next one, so reaching block 412 requires reading the two before it. Random access costs a traversal.

A file can grow by taking almost any free block and linking it to the chain. External fragmentation does not prevent growth because the blocks need not be adjacent.

Sequential traversal is straightforward, but direct random access is poor. Reaching logical block 10,000 can require following the chain from the beginning. Losing or corrupting one link can also disconnect the remainder.

The File Allocation Table, or FAT, design keeps the next-block links in a central table rather than inside each data block. That makes the chain easier to traverse when the table is available in memory, but a long file still has a per-block chain.

Linked allocation is historically important, but general-purpose Unix file systems favor indexed mappings that support direct lookup more effectively.

Indexed allocation stores block addresses in separate metadata.

A classic Unix inode has direct pointers for small files and indirect pointer blocks for larger files:

The index supports random access because the logical block number selects entries rather than requiring traversal through every earlier data block.

The cost is mapping metadata. A large contiguous file can require one address for every block even though the relationship is simply:

Extents compress that regular mapping.

Modern designs often combine ideas. An inode or mapping tree provides indexed lookup, while each leaf record describes a contiguous extent rather than one block.

An extent can be modeled as:

Consider this file mapping:

The logical layout is:

The storage layout is:

One extent record replaces eight separate addresses for the first run and four for the second.

The record captures two independent kinds of contiguity:

A fragmented file has more and shorter extent records. A well-placed file has fewer and longer ones.

A small file may fit its extent records directly in inode-associated space. As the file gains more extents, the file system can organize them in a tree.

Internal tree entries direct the search by logical block range. Leaf entries hold mappings.

Looking up logical block 10,600 does not scan every earlier extent. The tree selects the relevant leaf, and the matching extent computes the storage block by offset from its starts.

The exact tree shape and record format are file-system-specific. The general purpose is to keep lookup efficient while representing long runs compactly.

Suppose a file has:

Appending one block can extend the same extent when storage block 1,008 is available:

If that block is occupied, the allocator chooses another region:

Later adjacent allocation can sometimes merge compatible extents. Other operations can split them. Overwriting part of a sparse hole or punching a hole inside an existing run can turn one extent into several mapping records.

The file's logical byte sequence remains continuous where data exists. Extent boundaries are file-system metadata, not application-record boundaries.

A sparse file has logical ranges with no allocated data blocks.

Suppose:

The middle can be a hole:

Reading a hole returns zero bytes. The file system synthesizes those logical zeros without reading a stored zero-filled block for each position.

The extent mapping simply has no allocated extent covering that logical range.

Writing into the hole normally allocates storage for the affected range and creates or extends an extent.

Sparse is not the same as fragmented. A hole is an intentionally unallocated logical range. Fragmentation means allocated file data is divided among multiple storage runs.

Several tools answer different size questions.

ls -l and stat field st_size report the logical size:

du normally reports allocated storage associated with reachable file data:

du --apparent-size reports the logical byte view instead.

For a sparse file:

For an ordinary small file, allocation can exceed logical size because the final block is only partially used:

This unused capacity inside an allocated block is internal fragmentation. Bytes after EOF are not part of the file even if the allocated block has unused space.

File-system metadata, compression, sharing, reserved blocks, and implementation-specific accounting can make whole-file storage usage more nuanced. st_size remains the authoritative logical length, not a physical-usage total.

Before allocating an extent, the file system needs to know which blocks are free.

A free-space bitmap uses one bit per allocation unit:

Scanning consecutive zero bits can find a free run. Bitmaps are compact and support efficient machine-word operations.

For a 1 TiB file system with 4 KiB blocks:

Other designs track free extents in trees, ordered lists, or hierarchical allocators. A free-extent record can describe:

without one record per block.

Real file systems can divide storage into regions or allocation groups so multiple threads allocate concurrently without contending on one global structure. They can also keep related metadata and data near one another.

The specific data structure varies, but every allocator must answer:

When several free ranges are available, the allocator chooses among them.

Useful goals include:

Locality matters most visibly on hard disks because adjacent blocks reduce seek movement. It still matters on SSDs and remote storage because fewer extents can mean fewer mapping records, larger I/O requests, and less metadata work.

No policy can guarantee perfect placement under every workload. A nearly full file system with long-lived and differently sized files has fewer choices than a mostly empty one.

An application that knows a file's future size can ask the file system to reserve storage in advance.

On Linux, the fallocate utility exposes supported preallocation:

The corresponding system call lets programs request allocation for a range.

Preallocation can:

A file system can represent reserved but not-yet-written ranges as unwritten extents. Reads return zeros until actual data is written, preventing stale storage contents from becoming visible.

POSIX also provides posix_fallocate() as a portable interface for ensuring that space is available for a file range where supported.

Preallocation is not the same as writing application data, and it does not by itself make any later contents durable. It reserves mapping capacity.

Some file systems delay choosing exact storage blocks until they have more information about pending writes.

If an application grows a file through many small writes, allocating each 4 KiB block immediately can scatter the file:

By waiting, the allocator can see a larger logical range and choose one longer extent.

One allocation decision covering pending logical blocks 0 through 255 reserves a single 256-block storage run.

Delayed allocation improves placement opportunities and reduces metadata churn. It also means successful foreground writes do not necessarily imply that final storage addresses have already been assigned.

Implementations use reservations and accounting to manage free-space promises, but failures can still surface later in some workflows. Applications that require strong completion guarantees must use the relevant synchronization and error-reporting interfaces rather than assuming allocation timing from a successful buffered write.

The exact buffering and write-back path is separate from the allocation policy. The point here is that logical modification time and physical allocation time can differ.

External fragmentation means free space is divided into separated runs:

There is enough total capacity for a 12-block file, but no 12-block contiguous run. An extent-based file system can allocate several smaller extents, so the creation can still succeed at the cost of more fragmentation.

File fragmentation means one file's allocated data occupies multiple storage runs:

Internal fragmentation means allocated blocks contain unused capacity, commonly at the end of a file:

These are different problems. A sparse hole is different again: it is logical range deliberately lacking allocated blocks.

Fragmentation costs depend on the storage and workload. It can increase mapping metadata, split large sequential requests, cause extra seeks on HDDs, and make future large allocations harder. It does not automatically make a file unusable or corrupt.

A defragmenter tries to replace many small extents with fewer large ones.

Conceptually:

The file's logical bytes and pathname do not change. Its allocation mapping does.

Defragmentation needs enough free space to create better runs and can generate significant I/O. It is not automatically beneficial on every storage device or file system. Many modern allocators, delayed allocation policies, and workload patterns avoid severe fragmentation without routine manual defragmentation.

Use file-system-specific diagnostic and maintenance tools rather than assuming one universal defragmenter is safe.

Create a sparse 1 GiB file:

Compare its sizes:

A typical result shows:

truncate changed EOF without writing all the intervening zeros.

Now preallocate another file:

On a file system that supports fallocate, the apparent sizes can match while the reserved file consumes substantially more allocated space than the sparse file.

Inspect extent mappings with filefrag:

filefrag is commonly provided by the e2fsprogs package. Its usefulness and output depend on the file system and permissions. Some file systems provide their own mapping tools.

The reported storage addresses are file-system block addresses, not a guarantee about final physical flash or platter placement.

The following program writes five bytes at offset zero, seeks to 1 MiB, and writes three more bytes. The unwritten logical range between them becomes a hole when the file system supports sparse files.

Compile and run:

The logical size is:

The byte read from the middle of the hole is 0x00. The allocated block count depends on the file system but should commonly represent far less than the roughly 1 MiB logical size.

The program uses O_EXCL so it will not overwrite an existing path.

File allocation maps logical file blocks to file-system storage blocks. Contiguous allocation records one run but handles growth poorly. Linked allocation grows flexibly but makes random access expensive. Indexed allocation supports direct lookup but can require per-block metadata.

Extents combine indexed lookup with compact run descriptions. An extent records a logical start, storage start, and length. Small mappings can fit near the inode, while extent trees scale lookup to large and fragmented files.

Sparse holes are logical ranges without allocated blocks and read as zeros. Preallocation reserves storage before data is written, while delayed allocation postpones placement to make better extent choices. Logical size, allocated size, and apparent size therefore answer different questions.

Free-space bitmaps, extent trees, and regional allocators help file systems find blocks and preserve locality. Fragmentation can describe split free space, multiple runs within a file, or unused capacity inside allocated blocks; these are distinct conditions.

The central mental model is:

A file is logically addressed by byte offset, while allocation metadata maps only its stored ranges onto available file-system blocks.