Product SiteDocumentation Site

5.2. B+tree Extent List

Beyond the simple extent array, to efficiently manage large extent maps, XFS uses B+trees. The root node of the B+tree is stored in the inode's data fork. All block pointers for extent B+trees are 64-bit absolute block numbers.
For a single level B+tree, the root node points to the B+tree's leaves. Each leaf occupies one filesystem block and contains a header and an array of extents sorted by the file's offset. Each leaf has left and right (or backward and forward) block pointers to adjacent leaves. For a standard 4KB filesystem block, a leaf can contain up to 254 extents before a B+tree rebalance is triggered.
For a multi-level B+tree, the root node points to other B+tree nodes which eventually point to the extent leaves. B+tree keys are based on the file's offset. The nodes at each level in the B+tree point to the adjacent nodes.
The base B+tree node is used for extents, directories and extended attributes. The structures used for inode's B+tree root are:
typedef struct xfs_bmdr_block {
     __be16                     bb_level;
     __be16                     bb_numrecs;
} xfs_bmdr_block_t;
typedef struct xfs_bmbt_key {
     xfs_dfiloff_t              br_startoff;
} xfs_bmbt_key_t, xfs_bmdr_key_t;
typedef xfs_dfsbno_t xfs_bmbt_ptr_t, xfs_bmdr_ptr_t;
The subsequent nodes and leaves of the B+tree use the xfs_bmbt_block_t declaration:
typedef struct xfs_btree_lblock xfs_bmbt_block_t;
typedef struct xfs_btree_lblock {
     __be32                    bb_magic;
     __be16                    bb_level;
     __be16                    bb_numrecs;
     __be64                    bb_leftsib;
     __be64                    bb_rightsib;
} xfs_btree_lblock_t;
#define XFS_BMAP_MAGIC        0x424d4150        /* 'BMAP' */
The following diagram illustrates a single level extent B+tree:
The following diagram illustrates a two level extent B+tree:

xfs_db Example: