linux kernel 中的二叉树搜索 与 stl 相应物的对比

代码

Linux kernel 中也使用并实现了红黑树，但是查找算法没有自己实现，而是希望使用者去实现。如果只是实现一个精确查找的函数，这很简单，几乎每个人都能写出正确的代码：

static inline struct page * rb_search_page_cache(struct inode * inode,
						 unsigned long offset)
{
	struct rb_node * n = inode->i_rb_page_cache.rb_node;
	struct page * page;

	while (n)
	{
		page = rb_entry(n, struct page, rb_page_cache);

		if (offset < page->offset)
			n = n->rb_left;
		else if (offset > page->offset)
			n = n->rb_right;
		else
			return page;
	}
	return NULL;
}

这是 kernel 中 rbtree.h 中给出的示例代码，几乎所有的 kernel search 代码都遵循了这个模式。然而，这个代码的效率有问题，虽然仍是 O(logn) 的。

再看看 stl 中的实现(这只是个简化示例，不完全等同于 stl 中的实际代码)：

Node* rb_tree::lower_bound(const Key& k) {
  Node* y = NULL;
  Node* x = root;
  while (x != 0) 
    if (k <= x->key)
      y = x, x = x->left;
    else
      x = x->right;
  return y;
}
Node* rb_tree::find(const Key& k) {
  Node* y = lower_bound(k);
  return y == NULL || k < y->key ? NULL : y;
}

分析

kernel 代码的每个循环中有两个条件判断，而 lower_bound 中只有一个条件判断，虽然在 stl 中，即使在找到相应结点后，可能还需要再继续搜索，然而，鉴于二叉树（平衡树）的结构，深度越深的结点，其数目越多，对于满二叉树，深度增一倍，结点数目就增一倍，最底层（深度最深的那层）结点的数目比所有其它层的总数还要多1。假定满二叉树的高度为k（仅一个结点时定义该高度为0），则结点总数=2^(k+1)-1，针对查找成功的情况，假定每个结点被查找的概率相同，满二叉树的平均查找长度为：

linux kernel 的实现

(1*1+2*2+...+(k+1)*2^k))/(2^(k+1)-1) = (1 + k*2^(k+1))/(2^(k+1)-1) = k +(k+1)/(2^(k+1)-1)

(k+1)/(2^(k+1)-1) 在 k 较大时会非常快地趋近于 0，我们可以忽略这一项，结果就是k。

从而，最坏情况下，循环内的判断总次数为 2*k，平均次数是 1.5*k

stl::rb_tree::lower_bound

每个结点的查找都一直到最底层，所以平均查找长度为 k+1，只多 1，然而，循环内的判断次数是 1，所以总的判断次数是 k+1，rb_tree::find 在 lower_bound找到后需要再判断一次与key 是否相等，总的判断次数就是 K+2 了，但这仍然比 kernel 的判断次数少（k>2 的时候）。虽然这是针对满二叉树的分析，但这可以延伸至平衡的二叉树(log 的底数不再是 2，要比 2 稍微小一点)。

结论

现在应该看到了，虽然std::lower_bound 没有在找到目标的第一时间就返回，看上去似乎比较傻，但实际上要更快，鉴于现在 CPU 有缓存，分支预测（这个例子循环内的分支预测无法起作用，但CPU还有 speculation，就是同时执行两个分支，然后丢弃错误的那个分支），指令预取等高级功能，lower_bound 比 kernel 快的没有分析的那么多。经过实测，stl 的 rb_tree::find 要比 kernel 的大约快 10% 。

范围查找

如果要范围查找， kernel 的那个实现就不行了，而 lower_bound 是专干这个的（当然，还有个对应的 upper_bound）！

另外，毋庸置疑，stl 的这个代码更简洁，但稍微费脑子一点。