代码版本： v4.15.1

术语：

  • block：表示4KB的block。
  • BB：表示XFS的basic block概念，长度一般是512B。
  • 节点：表示btree中的一个节点，存储在一个block中。节点分为叶子节点和非叶子节点。
  • level：表示一个节点在btree中的层级，第0级是叶子节点，第N级节点的父节点是N+1级。
  • record：表示叶子节点中存储的数据。
  • key：非叶子节点中用来进行查找的key。
  • ptr：非叶子节点中存储的节点指针，用来表示一个节点的位置，因为一个节点就是一个block，所以节点指针的值是block number。

BTree的数据组织

XFS的btree的每个节点保存在一个block中，每个节点可以包含多个记录。节点分为叶子节点和非叶子节点。

叶子节点

BTree的叶子节点只需要保存数据。不同类型的btree的数据格式不一样，本文以BNO btree和CNT btree为例，所以叶子节点保存的数据的数据结构为xfs_alloc_rec_t。一个叶子节点的数据存储方式如下：

   header             data1                   dataN
+-----------------+-----------------+-----+-----------------+
| xfs_btree_block | xfs_alloc_rec_t | ... | xfs_alloc_rec_t |
+-----------------+-----------------+-----+-----------------+

叶子节点使用xfs_alloc_rec_t类型存储数据，因为是用来管理文件系统的block的，所以其内容就是代表一定数量的连续的block：

非叶子节点

BTree的非叶子节点保存key和节点指针。在BNO btree和CNT btree中，key的类型为xfs_alloc_key_t，节点指针的类型为xfs_alloc_ptr_t。

   header             key1                   keyN              ptr1                    ptrN
+-----------------+-----------------+-----+-----------------+-----------------+-----+-----------------+
| xfs_btree_block | xfs_alloc_key_t | ... | xfs_alloc_key_t | xfs_alloc_ptr_t | ... | xfs_alloc_ptr_t |
+-----------------+-----------------+-----+-----------------+-----------------+-----+-----------------+

在非叶子节点，header之后，先存储一定数量的key，这些key用于比较查找一个值在下一级节点的位置；key之后，存储和key数量一样多的ptr，每个ptr存储对应key所指向的下一级节点的block number。

节点header

不论是叶子节点还是非叶子节点，其header都是struc xfs_btree_block类型：

struct xfs_btree_block {
	__be32		bb_magic;	/* magic number for block type */
	__be16		bb_level;	/* 0 is a leaf */
	__be16		bb_numrecs;	/* current # of data records */
	union {
		struct xfs_btree_block_shdr s;
		struct xfs_btree_block_lhdr l;
	} bb_u;				/* rest */
};

重要数据结构

xfs_btree_cur

这个数据结构表示一个btree的游标，在btree进行搜索和修改操作时，需要用游标来跟踪当前节点在btree的路径。

xfs_btree_rec

这是一个 union，表示一个record，根据不同类型的btree访问不同的成员。

xfs_btree_key

这是一个 union，表示一个key，根据不通类型的btree访问不同的成员。

xfs_btree_ptr

这是一个 union，表示一个节点指针，可能是32位或者64位整数。一般是32位的。

xfs_btree_lookup(cur, dir, stat)

这个函数用于在btree中查找满足dir条件的记录，查找的值存放在cur->bc_rec中。

dir表示查找的方向，有三个值：

  • XFS_LOOKUP_LE：查找小于bc_rec中的值的记录。
  • XFS_LOOKUP_EQ：查找等于bc_rec中的值的记录。
  • XFS_LOOKUP_GE：查找大于bc_rec中的值的记录。

查找是要进行到叶子节点的，最后的查找结果会存放在cur->bc_ptrs[0]中，表示叶子节点的哪个record满足查找的条件，是否查找成功则通过stat参数返回。

xfs_btree_lookup_get_block(cur, level, pp, blkp)

这个函数读取pp指向的block，作为cur的第level级的节点，主要操作如下：

  1. xfs_btree_read_buf_block(cur, ptr, ..)读取当前cur和ptr所指向的block。
  2. xfs_btree_setbuf(cur, lev, bp)函数将bp设置到cur的lev层，表示cur的第lev层读取的是bp指向的节点。如果bp的左兄弟或者右兄弟不存在，那么设置cur->bc_ra[lev]的相应位。

xfs_lookup_get_search_key(cur, level, keyno, block, kp)

这个函数获取由block和keyno确定的key。如果是叶子节点，即level == 0，那么这个函数返回的其实是record的内容，因为叶子节点没有key。

Lookup的算法

  1. 从btree的根节点这一层开始
  2. 在每一层内执行二分查找：
    1. 如果该层内有key是匹配的，记录keyno，跳出二分查找。
    2. 如果该层内没有key是匹配的，则在搜索完该层的所有key后，记录最后的keyno，跳出二分查找。
    3. 如果当前层不是叶子节点，那么进入下一层继续搜索；如果当前层是叶子节点，那么结束对树的搜索。
  3. 根据最后一次比较的diff结果，以及参数dir，调整结果，并且返回查找是否成功。

xfs_btree_increment(cur, level, stat)

在(cur, level)指向的节点增加一个record，即在这个btree中查找指定record在同一级的右边的record，查找的过程可能需要调整每一级的节点。

  1. 首先处理最简单的情况，就是++cur->bc_ptrs[level] <= xfs_btree_get_numrecs(block)，即增加的record还在block的有效范围内，此时可以直接返回。
  2. 接下来获取当前节点的右兄弟。如果右兄弟不存在，那么说明我们已经处于这一层的最右侧节点，无法再继续increment操作。
  3. 然后开始向上层节点遍历，直到找到一个节点，右移一个record后还在节点内。找不到说明increment失败。
  4. 从上面找到的节点开始，向下遍历，调整每一层的节点，把ptr的位置指向新节点的第一个key。

理论上，这个函数也可以用于非叶子节点。

xfs_btree_decrement(cur, level, stat)

这个函数和increment操作差不多，只是方向相反，查找的是同一级左边的record。

xfs_btree_insert(cur, stat)

将一个record插入到cur指定的位置。

这个函数循环调用xfs_btree_insrec()函数插入一个record，然后判断是否发生了分裂，如果发生了分裂（此时key和父节点的ptr都已经被修改），那么就将游标向上移动一层，然后继续循环，直到不再发生分裂为止。

xfs_btree_insrec(cur, level, ptrp, rec, key, curp, stat)

将rec插入到(cur, level)指向的节点。因为插入一个记录可能导致节点的数据被移动，或者节点被分裂，所以这个函数会返回插入的物理位置。

当当前的节点空间不够时，会调用xfs_btree_make_block_unfull()函数来获得新的空间用于插入新的record。如果调用这个函数导致节点分裂，那么会产生新的游标，会通过curp返回。在分裂的情况下，这个函数并不会更新父节点的内容，但是会更新游标，以及指向新节点的key，由调用者负责更新父节点。

xfs_btree_make_block_unfull(cur, level, numrecs, oindex, index, nptr, ncur, key, stat)

通过移动数据或者分裂节点的方式，使得(cur, level)指向的节点有空间存放一个新的记录，这个操作会顺序尝试三个操作：

  1. 尝试将当前节点的最后一个记录右移一个节点：xfs_btree_rshift()。
  2. 如果右移不成功，则尝试将当前节点的第一个记录左移一个节点：xfs_btree_lshift()。
  3. 如果左右移动都不成功，则分裂当前节点为两个节点，即创建当前节点的右兄弟，然后把记录平分存储在两个节点中。
xfs_btree_rshift(cur, level, stat)

将cur指向的节点的最右侧record移动到右侧的节点，这样可以给当cur指向的节点空出一个位置。

xfs_btree_update_keys(cur, level)

更新从level + 1层往上的每个节点的key。只有当当前level的第一个位置（record或者key）发生变化时才需要更新，原因是btree节点的第一个位置的值是其父节点中的key，所以当第一个位置的值变化之后，需要更新父节点中对应的key，这样才能保证搜索可以正确执行。更新key的操作如下图所示：

update-keys

xfs_btree_split(cur, level, ptrp, key, curp, stat)

实际调用的是__xfs_btree_split()，将(cur, level)指向的节点分裂为两个节点。分裂之后，cur可能指向新节点，也可能指向旧节点，取决于原来的ptr落在哪个节点。

如果发生了分裂，那么有两个事情需要注意：

  1. 如果分裂前cur指向的位置现在位于新的block中，那么就需要更新cur->bc_bufs和cur->bc_ptrs对应内容。
  2. 如果cur当前指向的节点还有父节点，那么会复制一个游标到curp，并且把父节点的ptr右移一个记录，这个位置需要插入一个指针指向这次创建的节点。

该函数会通过ptrp返回新增的block的number，通过key返回新增的block的第一个record。

xfs_btree_delete(cur, stat)

xfs_btree_delrec(cur, level, stat)

先从当前节点删除ptr位置的数据，然后重平衡整棵树。这个函数会被xfs_btree_delete()调用多次，从level 0开始往上，直到不再需要重平衡为止。

xfs_btree_update(cur, rec)

更新当前cur指向的记录的值为rec的值。更新指定的记录之后，会调用函数xfs_btree_needs_key_update()判断是否需要更新父节点的key，对于标准的btree，只有当更新的是节点的第一个位置的记录的时候，才需要更新父节点的key。如果需要更新，则调用xfs_btree_update_keys()执行更新。

需要注意的是，这个函数并不检查更新后的数据是否满足btree的搜索正确性，这点由调用者保证。


知识共享许可协议本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。