#杂

我今天看sqlite btree的平衡实现，一个感想就是树形结构的实现比其他诸如链表、数组之类的结构复杂多了。

任何树形的数据结构，都要满足某种程度上的平衡，维持这个“平衡”的操作十分复杂。红黑树、B-Tree都需要在平衡被破坏之后，马上进行自下而上的平衡操作。比如截图中sqlite的负责平衡的函数，实现长达800多行，这还只是平衡算法其中的一种情况。

除此之外，中间的corner case的测试也很多，构造出测试的用例数据也难，如果不能覆盖所有场景，很难拍板说这个实现针对任何数据都是对的。

而链表之类的可就简单多了，除了头尾节点跟链表上的其他节点略有不同以外，其他都一致，这意味着边界情况很少。

这可能也是现在LSM类型的存储比Btree类型要流行得多的原因。