File systems

The big picture: two halves of one subject

To the computer, a file is just a long row of bytes (a byte is one small number, from 0 to 255). The computer does not know if the bytes are a photo, a song or a list of names. The meaning is decided by the programs that write and read them.

This subject has two halves. The first half is the work of the operating system: files, names, folders, placing the bytes on the drive, free space and crash safety. The second half is the work of the programmer who designs the inside of a file: records, indexes, B-trees, sorting and compression. Both halves obey the same law: the drive is slow, so we count drive accesses.

Words you will meet

Secondary storage: disks, flash and the cost of an access

Memory (RAM) is like the desk where you work: small, but anything on it is one second away. The drive, also called secondary storage, is like a library across town: huge, but every trip takes a long time. A typical memory access takes about 100 nanoseconds. A typical access to a magnetic disk takes about 10 milliseconds. That is a ratio of 100,000 to 1.

Because of this gap, the work the processor does between two disk accesses is almost free. What decides how fast a file program is, is how many disk accesses it makes. Indexes, B-trees and external sorting all come from this one fact.

Inside a magnetic disk

   a disk with 2 platters (4 surfaces)

   surface = a flat circle covered with magnetic material
   track   = one ring on a surface
   sector  = one slice of a track (often 512 bytes)
   cylinder = the same track on every surface,
              stacked like the rings of a tin can

        track 5 on surface 0   --+
        track 5 on surface 1   --+-- cylinder 5
        track 5 on surface 2   --+
        track 5 on surface 3   --+

The disk spins and an arm with a reading head moves in and out. The arm can read all the tracks of a cylinder without moving, so it pays to write a file along one cylinder before going to the next.

The capacity of a disk is the product: sector size x sectors per track x tracks per cylinder x number of cylinders. For example, 512 bytes x 32 sectors x 4 tracks x 100 cylinders = 6,553,600 bytes, which is 6.25 MiB (1 MiB = 2^20 = 1,048,576 bytes). The first PC BIOS could address at most 1,024 cylinders, 16 heads and 63 sectors, and that limit is where the old 504 MiB barrier came from.

The three parts of an access

One full turn takes 60,000 / rpm milliseconds, where rpm is turns per minute. A disk at 5,400 rpm needs 60,000 / 5,400 = 11.1 ms per turn, so the average rotational delay (half a turn) is about 5.6 ms. A faster disk, at 10,000 rpm, cuts it in the same proportion.

Seek and rotation are mechanical, so they are slow. Transfer is quick. So reading neighbouring blocks pays seek and rotation once, but reading scattered blocks pays them again every time. Take 100 blocks, a seek of 10 ms, a rotational delay of 5 ms and a transfer of 0.2 ms per block. Reading them in a row costs 10 + 5 + 100 x 0.2 = 35 ms. Reading them one by one in random places costs 100 x (10 + 5 + 0.2) = 1,520 ms. That is about 43 times longer, with the same data.

Blocking: many records per block

A disk read always brings a whole block, not one record. If a block holds 20 records (the blocking factor), a file of 6,000 records takes 300 blocks. A sequential search for a key that exists examines about half of the file on average, so it does about 150 reads, not 3,000. Blocking divides the reads by the blocking factor, but the search is still linear.

Flash memory (SSD)

A SSD has no arm and no spinning, so it has no seek. But NAND flash has a strange rule: it reads and writes in small pages, yet it can only erase a whole erase block (many pages together), and each erase block can be erased only a limited number of times.

• A page that already has data cannot be rewritten in place. The drive writes the new version in a free page, and marks the old page as invalid.
• The flash translation layer (FTL) is a small program inside the SSD. It keeps a table from the logical block that the file system asks for to the real page, so the SSD looks like an ordinary disk.
• Garbage collection copies the valid pages out of an erase block that is mostly invalid and erases it.
• Wear levelling spreads the writes over all blocks so that none wears out first.
• The TRIM command tells the SSD which blocks the file system has released, so the SSD does not copy dead pages for nothing.

Magnetic tape

On tape, every block is followed by an empty gap, because the tape needs room to stop and speed up again. The length used is S = n x (b + g), where n is the number of blocks, b is the length of data in one block and g is the gap. Example: 1,000 records of 100 bytes, at 1,000 bytes per inch, with a gap of 0.4 inch. One record per block: b = 0.1 inch, S = 1,000 x 0.5 = 500 inches. Ten records per block: n = 100, b = 1 inch, S = 100 x 1.4 = 140 inches. Blocking makes the tape 3.6 times shorter, because there are ten times fewer gaps.

Files, attributes and operations

When you write fopen("clientes.dat", "r") in C, two different things meet. The physical file is the real row of bytes that the operating system keeps on the drive. The logical file is the name your program uses for it, for example the variable fp of type FILE *. The open operation ties them together. The same program can be tied to a different physical file just by changing the name.

What is inside: bytes, and file types

UNIX and Windows treat a regular file as a plain sequence of bytes. The system does not know what the bytes mean, so fields, records and lines are decided by the application. This is the most flexible model, and that is why it won. The system knows only a few file types: regular files, directories, and special files that stand for devices (character special for keyboards, block special for disks). Among regular files, the only format the kernel really must understand is the executable, and it recognises it by the magic number at the start of the file. A file extension such as .txt is just a habit that programs may follow or ignore.

Attributes

Besides its bytes, a file has facts about it, called attributes or metadata: size, owner, permissions, the number of links, and three timestamps. The facts live in the file's i-node, not in the file's bytes.

Operations and the current offset

Every open file has a current offset: the place where the next read or write happens. read and write move it forward. lseek only changes the offset. It does no input or output, so it is cheap. The real cost appears on the next read, when the system turns the offset into a block and fetches it from the drive (unless it is already in the cache).

Opening modes of fopen

Descriptors, open-file entries and i-nodes

process table            open-file table        i-node table
(per process)            (shared by system)     (one per file)

 fd 3 ------------+--->  entry A: offset 2 ----+
 fd 4 (dup of 3) -+                            +--> i-node of f
 fd 5 ----------------->  entry B: offset 0 ----+

There are three levels. A descriptor is a small number in the table of the process. It points to an open-file entry, which holds the current offset and the opening mode. That points to the i-node, which has the attributes and the blocks. dup and fork copy the descriptor, so both copies share one entry and one offset. A separate open of the same file makes a new entry with its own offset.

// the file holds the bytes 0123456
int a = open("f", O_RDONLY);
int b = dup(a);                 // same open-file entry as a
int c = open("f", O_RDONLY);    // a new entry, offset 0
char buf[2], x, y;
read(a, buf, 2);                // buf = '0','1'; shared offset is now 2
read(b, &x, 1);                 // x = '2', because the offset is shared
read(c, &y, 1);                 // y = '0', because c has its own offset

This is why a parent and a child process, after fork, write one after the other into the same output file instead of writing over each other.

Two layers of buffer

• The C library buffer lives in the memory of your process. fwrite puts bytes there to avoid one system call per call. fflush or fclose sends them to the kernel. If the process is killed first (for example by SIGKILL), these bytes are lost.
• The kernel cache (page cache) receives the bytes on write and survives the death of the process. fsync forces it to the drive. These bytes are lost only if the whole machine fails first.

Sparse files and memory mapping

If you create an empty file, lseek to offset 40,960 and write one byte, the file becomes a sparse file. Its logical size (shown by ls -l) is 40,961 bytes, but with 4 KB blocks only the block that holds that last byte is allocated, so du shows one block. The skipped part is a hole, and reading inside it returns zeros without touching the disk. Copying a sparse file byte by byte can fill a disk.

With mmap a process can map a file into memory: a range of addresses corresponds to the bytes of the file, and the system loads pages when they are touched (demand paging). There is no copy between the kernel cache and a buffer of the program, and random access is simple. But the program no longer decides when the data reaches the drive, unless it calls msync.

Allocation: contiguous, linked, FAT and i-nodes

A file may need many blocks. Allocation is the choice of which blocks of the drive belong to which file, and how the system remembers it. There are four classic answers.

1. Contiguous allocation

The file lies in a row of neighbouring blocks. The directory entry needs only two numbers: the starting block and the number of blocks. The address of block k is start + k, one addition. So random access and sequential reading are very fast. The problems: a file that must grow may find no room after it, and when files are deleted the free space is chopped into holes. This is external fragmentation: the total free space may be enough, but no hole is big enough for a new file. The cure, compaction, is expensive.

2. Linked allocation

Each block carries the number of the next block, and the directory holds the number of the first. Any free block can be used, so there is no external fragmentation. But to reach logical block k (counting from 0) the system must read blocks 0, 1, ... up to k, because every pointer is on the disk: that is k + 1 reads. Also, the pointer takes a few bytes of every block, so the data part is no longer a power of two, which annoys programs that read whole blocks.

3. FAT (file allocation table)

The FAT takes all the pointers out of the blocks and puts them in a table with one entry per disk block. Entry i says which block follows block i, or marks the end or a free block. The whole block is now free for data, and the system follows the chain in memory.

entry:   0     1     2     3     4     5     6     7
value:   -     5     EOF   FREE  1     2     FREE  -

file starts at block 4 (from the directory):
   4 --> 1 --> 5 --> 2 --> EOF       file = blocks 4, 1, 5, 2

The price: the entire table must be in memory, and it is as big as the disk, not as the number of files in use. The width of the entry limits the volume: FAT-12, FAT-16 and FAT-32 use 12, 16 and 28 bits of address. The largest volume is the number of clusters x the cluster size. Example: 12-bit entries and 4 KB clusters give 2^12 x 2^12 bytes = 16 MiB. That is why bigger volumes needed bigger clusters (more waste), until the entry was widened.

4. I-nodes

An i-node is a small card for one file: its attributes plus the addresses of its blocks. Only the i-nodes of files in use need to be in memory, so the memory needed is proportional to the number of open files, while a FAT is proportional to the size of the disk. That is the big advantage.

The i-node has a few direct pointers to data blocks, then a single indirect pointer (to a block full of pointers), a double indirect (a block of blocks of pointers) and a triple indirect. Small files, which are the majority, live entirely in the direct pointers. A block holds (block size / pointer size) numbers. With 1 KB blocks and 4-byte numbers that is 256.

How to find a byte, step by step. Take 2 KB blocks, 4-byte numbers (so 512 numbers per block) and 8 direct pointers, and find the byte at offset 3,000,000. First turn the offset into a logical block: 3,000,000 div 2,048 = 1,464. The direct pointers cover blocks 0 to 7, the single indirect covers 8 to 519, and the double indirect starts at 520. So the block is in the double indirect area at position 1,464 - 520 = 944. Split 944 by 512: quotient 1, remainder 432. Read the double indirect block, take its entry 1, read that block, take its entry 432, and read the data block.

Convention used in this summary and in the quiz: the i-node is already in memory and nothing is cached, and the count of blocks read includes the data block. So the example above reads 3 blocks: the double indirect, one single indirect, and the data. A direct block costs 1 read, a single indirect costs 2, a double 3 and a triple 4.

The largest file is the smallest of three independent limits: how much the pointer tree can reach, how many blocks the block-number width can name, and how large a number the size field of the i-node can hold. Real systems were limited by each one in turn, which is why size fields moved to 64 bits.

Extents, i-node shortage and small files

• An extent (called a run in NTFS) records a stretch of contiguous blocks with two numbers: the start and the length. A file in few pieces needs very little metadata. It is a middle path between contiguous allocation and one pointer per block. ext4 and NTFS use it.
• A classic UNIX volume has two things that can run out: data blocks and i-nodes. The number of i-nodes is fixed when the disk is formatted. A disk full of tiny files can say 'no space left' when creating a new file although thousands of blocks are free. The command df -i shows the i-nodes.
• In NTFS, everything about a file is an attribute of its record in the MFT, the data included. A tiny file (say 200 bytes) is stored inside the MFT record (resident). Big data goes to clusters described by runs (non-resident).

Fragmentation: the two kinds

Internal fragmentation is space that is given to a file and not used by it: the leftover in its last block. Example: clusters of 4,096 bytes, files of 100, 5,000 and 8,192 bytes. They take 1, 2 and 2 clusters, so the waste is 3,996 + 3,192 + 0 = 7,188 bytes. On average half a block is lost per file. External fragmentation is free space cut into pieces between files that are too small to use.

Directories and links

You do not want to remember that your homework is in i-node 48,213. You want to call it homework.txt. A directory is the thing that joins names to files. In a classic UNIX file system a directory is just a table of pairs: a name and an i-node number. The attributes and the block addresses live in the i-node, not in the directory entry.

Paths

An absolute path starts at the root / and does not depend on where the process is. A relative path is resolved from the working directory of the process. Every directory has two special entries: . (the directory itself) and .. (its parent). They are ordinary names stored in the directory. So if the working directory is /home/ana, the path docs/../notes.txt goes into docs, back up, and ends at /home/ana/notes.txt.

How the system resolves a path

To open /usr/ast/mbox the system walks the path name by name. For each name it needs two reads: the block of the current directory (to find the i-node number of the next name) and then that i-node (to learn where the blocks of the next level are).

open("/a/b/c")      root i-node already in memory

 1. read block of /      -> finds i-node number of a
 2. read i-node of a
 3. read block of a      -> finds i-node number of b
 4. read i-node of b
 5. read block of b      -> finds i-node number of c
 6. read i-node of c     -> now in memory

This is why systems keep a name cache. We assume every directory fits in one block.

Hard links and symbolic links

The link count

The i-node keeps a link count: how many directory entries point to it. When a name is removed (unlink) the count goes down, and when it reaches zero (and nobody has the file open) the system frees the file. For a directory: one link comes from its name in the parent, one from its own . entry, and one from the .. entry of each direct subdirectory. So an empty directory has a count of 2, and a directory with 3 subdirectories has 2 + 3 = 5. The count minus 2 is the number of subdirectories.

Why can an ordinary user not make a hard link to a directory? Because the count works as the rule 'free it at zero' only when the directory graph has no cycles. A cycle would keep a count above zero for something nobody can reach, and a garbage collector would be needed to find it. A symbolic link may point to a directory because it does not enter the count, and programs that walk the tree can simply refuse to follow it.

Moving a file

mv inside one file system calls rename: it adds an entry in the new directory and removes the old one. No data block is touched, so moving a 4 GB file is instant. Across two file systems the i-node number is not valid, so the system must copy the data and delete the original.

Free space management and journaling

When you save a new file, the system must find empty blocks. So it needs a record of which blocks are free. There are two classic ways.

Bitmap

A bitmap has one bit per block: 1 means used, 0 means free (or the other way round). Its size is fixed, whatever the occupancy of the disk, and it makes it easy to find neighbouring free blocks, which keeps files contiguous. Example: a disk of 2^38 bytes (256 GB) with 4 KB blocks (2^12 bytes) has 2^26 blocks, so the bitmap has 2^26 bits = 2^23 bytes = 8 MiB, which fits in 2^23 / 2^12 = 2,048 blocks. It costs about 0.003% of the disk.

Linked list of free blocks

The free blocks are kept in a list. Each block of the list holds many free block numbers and one pointer to the next list block. With 2 KB blocks and 32-bit numbers, a list block holds 512 numbers: 511 free block numbers and 1 pointer. To record 102,200 free blocks you need 102,200 / 511 = 200 list blocks. The cost grows with the free space, not with the disk size, and the list can live inside the free blocks themselves, so it takes nothing from files.

Which is smaller? The bitmap costs B bits for a disk of B blocks. The list costs 32 bits per free block. The list wins only if 32 x (free blocks) < B, that is, when less than 1/32 of the disk (about 3%) is free. That is almost a full disk, so the bitmap is the common choice.

Crashes: why one operation is many writes

Deleting a file in a UNIX file system without a journal takes several writes at different places of the disk: (1) remove the directory entry, (2) free the i-node, (3) return the data blocks to the free list. The power can fail between two of them.

The order of the writes decides the damage. Releasing things last can only lose space, which is better than leaving a name that points to something already released. The space comes back only after a full check with fsck.

The consistency checker

fsck builds two tables with a counter per block: how many times the block appears in some file, and how many times it appears in the free list. On a healthy disk every block has exactly (1, 0) or (0, 1).

Journaling (write-ahead logging)

A journal is a diary. Before touching the real structures, the system writes in the diary what it is about to do. Only after the diary entry is safe does it make the real changes. When they are done, the entry can be thrown away.

 1. write the intended changes into the journal
 2. write a COMMIT record   <-- the operation now counts
 3. apply the changes to their real places
 4. free the journal entry

 crash before 2 : no commit -> discard the entry (nothing happened)
 crash after 2  : commit    -> redo the entry (it all happens)

After a crash the system reads the journal, redoes the committed transactions and discards the ones without a commit record. That is much faster than scanning the whole disk.

Many file systems journal only metadata (i-nodes, directories, block maps): the journal stays small and fast, and the structures always return to a consistent state. But the content of a file that was still in the cache may be lost. Durability of the content needs fsync or a mode that journals data too, which writes each block twice.

Quotas

To stop one user from filling the disk, the system keeps for each user the current use of blocks and i-nodes and two limits. The soft limit can be exceeded for a short time (the user gets warnings). The hard limit can never be exceeded: the allocation simply fails.

Record organisation: fixed, variable, RRN

Suppose a program writes names and cities one after the other and the file looks like AnaSilvaRecifeBrunoLimaNatal. Where does the name end and the city begin? Nobody can tell. A file is just bytes, so the program must write the structure down. There are four classic ways to separate fields:

• Fixed-length fields: every field has the same number of bytes, padded with spaces.
• Length indicator: a number before each field says how many bytes it has.
• Delimiter: a special character such as | after each field.
• Keyword and value: pairs such as city=Recife.

Fixed-length records and the RRN

If every record has the same size, the position of any record is computed, not searched. The RRN (relative record number) is the ordinal number of the record in the file. In this course the RRN starts at 0. If the file has a header of H bytes and each record has R bytes, the record with number RRN starts at byte

offset = H + RRN x R

example: H = 32, R = 100, RRN = 7
offset = 32 + 7 x 100 = 732

byte 0       32        132       232
     +--------+---------+---------+---------+
     | header | RRN 0   | RRN 1   | RRN 2   | ...
     +--------+---------+---------+---------+

One seek goes straight to the record: constant time. This is the reason why direct access by RRN requires fixed-length records. Also, the number of records in a file is (file size - header) / record size. If the division is not exact, the file is damaged. Example: a file of 4,032 bytes with a header of 32 and records of 100 has (4,032 - 32) / 100 = 40 records.

The price is internal waste: every field is sized for the biggest value expected, so the leftover is padding. If a record has fields of 30, 20 and 14 bytes (64 in total) and the values use 3, 6 and 11 bytes, 64 - 20 = 44 bytes are padding.

Variable-length records

Here each record has only the size it needs, often with a length indicator at the start. The file is smaller, but you lose direct access: the start of the next record is known only after reading the indicator of the current one. Example: records of 1 + 4, 1 + 7 and 1 + 3 bytes start at offsets 0, 5 and 13. To reach the 500th record you must walk through 499 records, so the time is proportional to n. The fix is a separate index with the offset of every record.

The header record

A header record at the start of the file holds facts about the whole file: a magic number, a version, the record size, the number of records, and so on. It makes the file self-describing: whoever opens it reads the header first and learns how to read the rest. The price is that the first data record no longer starts at byte 0.

Byte order (endianness)

A number of 4 bytes can be stored with the big end first (big-endian) or the little end first (little-endian). If a program writes an integer by copying its bytes from memory, the file depends on the machine. The number 258 is 0x00000102. A big-endian machine writes the bytes 00 00 01 02. A little-endian machine that reads those bytes straight into an integer builds 0x02010000 = 33,619,968. A portable format fixes the byte order of each field, and programs convert on reading and writing. With one agreed format, N architectures need 2N converters instead of one for each pair.

The canonical form of a key

A search compares bytes. 'maria silva', 'MARIA SILVA' and 'Maria Silva ' look the same to you but not to the computer. The canonical form is the single, agreed way to write a key (for example capital letters, no accents, no extra spaces). Every program applies it before writing and before searching.

Compression and reclaiming space

What happens to the space of a record you delete? There are three answers, from the lazy one to the tidy one.

1. Mark it as deleted and do nothing else. It is fast and can be undone. The space is still there, wasted.
2. Compaction: from time to time, rewrite the file without the marked records. The space returns, but the addresses change, so the indexes must be rebuilt.
3. Reuse the space on the next insertion, using a list of free records.

Fixed-length records: the free list as a stack

With fixed-length records any free slot fits any new record, so a stack is enough. The header holds the RRN of the top. Each deleted slot holds the RRN of the one below it. Delete = push. Insert = pop. The list takes no extra space, since it lives inside the free slots. The file grows only when the stack is empty.

start: top = -1 (empty)
remove RRN 4   -> stack (top first): 4
remove RRN 1   -> stack: 1, 4
insert P       -> P goes to RRN 1, stack: 4
remove RRN 6   -> stack: 6, 4
insert Q       -> Q goes to RRN 6, stack: 4
insert R       -> R goes to RRN 4, stack: empty (top = -1)
insert S       -> stack empty, so S goes to the end of the file

Variable-length records: which hole to use?

Now the holes have different sizes, so the system must choose one that fits. Take a free list 50 -> 25 -> 90 -> 35 (sizes in bytes) and a new record of 30 bytes.

Best-fit leaves tiny leftovers that no record can use (if the smallest record is 10 bytes, a leftover of 5 is useless). Worst-fit tries to keep the leftover useful. No strategy removes external fragmentation, so we still join neighbouring holes and compact.

To be clear about the two kinds of waste in a file of records: internal fragmentation is the waste inside an allocated area (the padding of a fixed-length record). External fragmentation is the waste between allocated areas, in holes too small to use. Fixed-length records suffer only the internal kind. Variable-length records trade the internal for the external.

Compression: making the file smaller

Compact notation. Replace a readable value by a binary code with just enough bits. For n different values you need ceil(log2 n) bits. For 100 values: 2^6 = 64 is too small and 2^7 = 128 is enough, so 7 bits. The file shrinks, but a text editor can no longer read it, and every program needs the code table.

Run-length encoding (RLE). A run of equal bytes becomes a short code: a marker, the value and the count. In the version used here a run of 4 or more equal bytes becomes 3 bytes, and shorter runs are copied as they are (a code of 3 bytes is not worth it for 2 or 3 bytes). Example, with marker FF: the bytes 41 41 41 41 41 42 43 43 become FF 41 05 (the five 41), 42, 43 43, which is 3 + 1 + 2 = 6 bytes instead of 8. Data with no repetition does not shrink. RLE works well on images with uniform areas and on records full of padding.

Huffman coding. Give short codes to frequent symbols and long codes to rare ones. Build a tree: join the two least frequent nodes into a new node whose weight is their sum, and repeat until one tree is left. The code of a symbol is its path from the root (left = 0, right = 1).

frequencies: A 40, B 30, C 20, D 10  (total 100)

 step 1: C + D = 30
 step 2: B + (CD) = 60
 step 3: A + 60 = 100

            (100)
            /   \
          A(40)  (60)          A = 0
                 /  \          B = 10
               B(30) (30)      C = 110
                     /  \      D = 111
                  C(20) D(10)

The size of the encoded file is the sum of frequency x code length: 40x1 + 30x2 + 20x3 + 10x3 = 190 bits (a fixed 2-bit code would need 200). A shortcut: the sum also equals the weights of all the internal nodes, 30 + 60 + 100 = 190. A Huffman code is prefix-free: no code is the beginning of another. That matters because the decoder must know where each code ends. With the prefix property, reading left to right is never ambiguous and no bits are spent on separators. In the tree it simply means the symbols are only at the leaves.

These numbers were measured in this repository, on a file of fixed-length records with a lot of padding. RLE removes the padding and Huffman exploits the unequal frequencies of the bytes, and using one after the other is best.

Indexes: primary, secondary, inverted lists

Finding a record by reading the whole file is slow. A book solves this with a table of contents at the front. An index is that table for a data file.

The simple (primary) index

A simple index is a list of small fixed-length entries (key, address of the record), sorted by the key. The data file stays in the order the records arrived. The index separates two things: the search order (in the index) and the data (unchanged). The address can be an RRN or a byte offset.

Why binary search works on the index but not on the data file: it needs the items in key order and a way to jump to the middle one. Variable-length records in arrival order offer neither. The index offers both, and gives the address, so the record is read with one seek.

A binary search discards half of what is left at each step. For N entries the worst case is floor(log2 N) + 1 examined entries. Example: N = 1,000 and 2^9 = 512 < 1,000 <= 1,024 = 2^10, so at most 10 entries. In memory this is nothing. But if the index is on disk, 10 or 17 accesses per search are still a lot, and that is why B-trees exist.

Keeping the index correct

If the index is kept in memory and written to disk only when the file is closed, there is a danger: the program may fail and leave the disk index old. The solution is an out-of-date flag in the header of the index file. Set it on disk before the first change of a session, clear it when the index is written. If the flag is set when the file is opened, the last session did not end well. Since the index can be built from the data, the program rebuilds the index by reading the data file.

Secondary indexes

The primary key identifies one record. But people ask by other things: all the songs of one composer, all the customers of one city. A secondary index is sorted by such a field. Since the value can repeat, the answer is a list of records.

Inverted lists

In an inverted list the secondary index has one fixed-length entry per secondary key, with the position of the first element of a linked list. The list lives in another file. Each element holds a primary key and the position of the next element (-1 means the end).

secondary index          list file (position: primary key, next)
CITY -> head
NATAL  -> 2              0: P40, 3
RECIFE -> 0              1: P77, -1
                         2: P10, 1
                         3: P55, -1

search RECIFE: start at 0 -> P40, go to 3 -> P55, next -1: end
result, in list order: P40, P55

Adding a record appends one element to the list file and changes one pointer. Nothing is shifted. The price: the elements of one list are scattered over the file.

The list holds primary keys, not addresses. This is called late binding: the address is found only at search time, going through the primary index. A secondary search costs one more lookup, but when the data file is compacted and the records change address, only the primary index must be fixed. The secondary indexes stay correct because the primary keys did not change.

Combining searches: cosequential processing

If each list is sorted by primary key, two lists can be combined in one single pass. Compare the current item of each list and advance the one with the smaller key. Take CITY = RECIFE -> 10, 20, 30, 40 and YEAR = 2020 -> 20, 25, 40, 50, 60.

• AND (matching): keys that appear in both lists: 20 and 40. That is 2 keys.
• OR (merging): every key seen, once: 10, 20, 25, 30, 40, 50, 60. That is 4 + 5 - 2 = 7 keys.
• Only after combining the lists are the records read, and only those that matter.

This repository's file-organisation mini-project builds exactly this: 10,500 records, a primary index searched with at most 14 probes, and a search by city that reads about 880 slots through the index, against 10,500 for a full scan.

B-trees

A binary search tree has two children per node and can be tall: a million keys need about 20 levels. On a disk each level is one access, so 20 accesses is too many. The trick is to make each node as big as one disk page and put hundreds of keys in it. This is the B-tree.

Order and the rules

In this summary the order m is the maximum number of children of a node (books differ, so always say which definition you use). The rules:

• A node has at most m children and so at most m - 1 keys. The keys in a node are in order, and the subtrees fall between them.
• Every node except the root has at least ceil(m/2) children, so at least ceil(m/2) - 1 keys. Order 8: from 4 to 8 children, so from 3 to 7 keys.
• The root has at least 2 children (unless it is a leaf).
• All the leaves are at the same level.

A tree with h levels, all nodes full, has 1 + m + m^2 + ... nodes, each with m - 1 keys, which gives m^h - 1 keys. The capacity grows exponentially with the height. Order 5 and 3 levels: 5^3 - 1 = 124 keys.

Choosing the order

On disk the order is the largest number of children that fits in one page. Example: a page of 4,096 bytes, a header of 12 bytes, keys of 4 bytes and pointers of 4 bytes. We need 12 + 4(m - 1) + 4m <= 4,096, so 8m <= 4,088 and m <= 511. Check: 12 + 4 x 510 + 4 x 511 = 4,096. Smaller keys give a larger order and a shorter tree. This is why indexes prefer short keys.

How tall can the tree be?

The worst case is when every node has the minimum. Call c = ceil(m/2). The root has 1 key and 2 children, and the other nodes have at least c - 1 keys. Take order 10 (c = 5). With 3 levels the least number of keys is 1 (root) + 2 x 4 (two nodes) + 10 x 4 (ten nodes) = 49, and with 4 levels it is 249. So a B-tree of order 10 with 100 keys can have at most 3 levels. For order 200 and a million keys, the tree has at most 3 levels: a search reads at most 3 nodes, and 2 if the root stays in memory.

Insertion: always in a leaf, and splitting

A new key goes to the right leaf. If the leaf now has too many keys (overflow), it is split: the middle key goes up to the parent and the rest form two nodes. If the parent overflows, it splits too. If the split reaches the root, a new root with a single key is created. This is the only way a B-tree grows in height. That is why all leaves stay at the same level: the tree grows from the top, as a consequence of how it is built, not by a repair afterwards.

Convention of the quiz: a node 'overflows' when it gets one key more than the maximum (m keys). Then the middle key goes up. With an even number of keys, the left node keeps the first half and the key right after goes up.

order 4 (max 3 keys). Insert 8 into the leaf [5 | 6 | 7]:

   before:        [ 20 ]                  leaf [5 | 6 | 7] is full
                  /    \
          [5|6|7]      [30|40]

   leaf gets 4 keys: 5 6 7 8  -> overflow
   split: left [5|6], third key 7 goes up, right [8]

   after:         [ 7 | 20 ]
                 /    |     \
            [5|6]   [8]   [30|40]

Removal

1. Key in an internal node: replace it with its successor (or predecessor), which is always in a leaf, and remove that one. So every removal ends in a leaf.
2. Leaf below the minimum: first try redistribution. If an adjacent sibling has more than the minimum, the separator in the parent comes down into the leaf and the nearest key of the sibling goes up to replace it.
3. If no adjacent sibling can give a key, do concatenation: join the leaf, the separator and the sibling into one node. The parent loses a key and may underflow too, so the problem can move up.

The B+ tree

In a B+ tree the internal nodes hold only copies of keys to route the search (no data), and all the keys and data are in the leaves, which are linked in order. Because internal nodes carry no data, more separators fit per page, so the tree is shorter. For a range query (all keys from 100 to 900) you search the first key, then follow the leaf links without going back up: one access per leaf. That is why databases use B+ trees for range queries and for sorting by an indexed field.

External sorting

How do you sort a file that is bigger than the memory? If you load it all, the program dies. If you sort it in place by jumping around, every comparison is a disk access, and that is 100,000 times slower than memory. External merge sort keeps two promises: memory use does not depend on the size of the file, and the file is always read and written in sequence.

Phase 1: generate runs

Read a piece as big as the memory, sort it in memory and write it out as a run: a sorted file. Repeat until the input ends. If the file has N records and the memory holds M, the number of runs is ceil(N / M). Example: 2,000,000 records and room for 150,000 gives 2,000,000 / 150,000 = 13.3, so 14 runs (13 full and one smaller).

Phase 2: merge the runs

Read all runs from start to end at once. Always write the smallest of the current front records. A min-heap holds one entry per run (that run's current record). The top is the smallest: write it, read the next record of the same run, and let it sink to its place. This costs about log2 k comparisons per record, instead of k - 1 by looking at all the k fronts. A heap of 64 items has 6 levels, so a record goes down at most 6 steps, not 63 comparisons. The memory used is proportional to k, not to the file.

run 0:  3  8  9 ...     heap holds the front of each run:
run 1:  1  4  7 ...     [ 3 , 1 , 2 ]   smallest = 1 (run 1)
run 2:  2  5  6 ...     write 1, read 4 from run 1:
                        [ 3 , 4 , 2 ]   smallest = 2 (run 2) ...

output: 1 2 3 4 5 6 ...

Several passes

If memory allows only k runs at a time (the fan-in), a merge pass joins groups of k runs into longer ones. After a pass the number of runs is ceil(R / k). The number of passes is ceil(log base k of R). Example: 60 runs with fan-in 4: 60 -> 15 -> 4 -> 1, that is 3 passes. We do not count run generation among the merge passes.

Each pass reads and writes the whole file once, and so does run generation. So an external sort with 2 merge passes moves the file 3 times in each direction: for a file of 8 GB that is 3 x 8 = 24 GB written. The number of passes is the real cost.

The trade of a large fan-in

A bigger fan-in means fewer passes. But the memory is split among the k input buffers, so each buffer is smaller and is refilled more often. On a magnetic disk every refill from a different run is a seek. Merging 800 runs in one go can be slower than merging in two steps (for example 25 groups of 32 runs, then the 25 results), although the second way reads and writes everything twice: its reads are longer and more sequential.

These results come from the external-sorting mini-project of this repository (mean of 7 runs). Going from fan-in 2 to 16 cuts the passes from 6 to 2 and the time by about half. Fan-in 64 saves one more pass but is not faster, because the memory is split in 65 small buffers. The spread between runs was large on a shared machine, so small differences are not real differences.

Replacement selection: longer runs

A smarter phase 1 uses a heap of M records. Write the smallest record of the heap, then read a new record in its place. If the new record is smaller than the one just written, it cannot join the current run, so it is held back for the next run. The result depends on how ordered the input already is:

Example: 50,000 records in decreasing order and M = 1,000 give 50 runs. Fewer runs mean a cheaper merge.

Putting it all together

Every idea in this area answers one question: how do I keep the number of drive accesses low? Here is the whole story in one table.

Mistakes to avoid

• Thinking lseek reads the disk. It only changes the offset.
• Thinking ctime is the creation date. It is the last change of the i-node.
• Thinking a hard link can cross partitions. The i-node number only has meaning inside one file system.
• Forgetting the data block when you count the reads of an i-node lookup, or forgetting that the i-node is already in memory by assumption.
• Starting the RRN at 1 when the problem says 0, or forgetting the header when you compute an offset.
• Forgetting the plus 1 in the binary search worst case, floor(log2 N) + 1.
• Mixing the order of a B-tree (children) with the number of keys (one less).
• Thinking a journal protects the content of your files. A metadata journal protects the structures.

Where to learn more

• Operating Systems: Three Easy Pieces has free chapters on disks, files, file system implementation, journaling and flash.
• Files are hard, by Dan Luu, shows how hard it is to write a file safely.
• ext4 Data Structures and Algorithms describes the real layout of a production file system.
• SQLite Database File Format shows how tables and indexes are stored as B-tree pages in one file.