Managing RAID on Linux

Organization

Different filesystems implement different methods for organizing data. Traditional Unix filesystems relied on linked lists to organize inodes and data blocks. A table of inodes pointed to a physical disk block. This arrangement obviously doesn’t scale well. So, newer filesystems have sought to optimize the process. ext2, for example, applies a block bitmap and splits up the inode table so that it is distributed across the entire disk. Rather than look up a data block from a single, large table, a filesystem such as ext2 needs to examine only a small subset of inodes to perform I/O.

As the complexity of applications and operating systems has evolved, so has filesystem design. Today, many new filesystems implement a data structure known as a B-tree to organize the filesystem. B-trees have been used in database design for many years. A B-tree is optimized so that it can be quickly accessed, even when it’s stored on a hard disk. This usually means that the size of a leaf in a B-tree is equal to, or is some function of, the size of a filesystem data block.

A B-tree is similar to a balanced binary tree, with a few notable exceptions. B-trees have a large branching factor. Where a binary tree has only two leaves per node, a B-tree can have many, which makes the path to access data much shorter. In turn, the height of a B-tree is small, compared with a traditional binary tree. Some filesystems use B-trees exclusively, while others implement a combination with the traditional ...