存储引擎数据结构优化(1):cpu bound

一个存储引擎的性能瓶颈，一般可以归为两类：cpu-bound或io-bound。
cpu-bound表现在cache层，io-bound表现在index层。
在存储引擎里，cpu(memory)很便宜，而一次io太“昂贵”了。
一个好的存储引擎应该是cpu-bound的，而不是io-bound的。
cpu-bound:
你的存储引擎性能跟cpu快慢相关，cpu越快，性能就越好，而跟磁盘的io能力关系不是很大。
io-bound:
你的存储引擎性能跟磁盘的io能力相关，磁盘io能力越强，性能就越好。
假设你的存储引擎在io能力为100 iops的磁盘上为1000 writes/sec，而在200 iops的磁盘上为2000writes/sec… 说明它非常依赖磁盘io 能力！
大家常说：机械磁盘的随机io能力差，所以存储引擎表现不佳。
其实这个观点带有片面性，那是因为你对hdd的优化还远远没有发挥到“极致”，使之成为cpu-bound型的存储引擎！
本文就先谈下cpu-bound上数据结构的优化，下篇再谈针对io-bound的优化。
先罗列下在cache里用的比较多的数据结构：
1) red-black tree
我认为它的“平衡”主要是针对“读优化”，并非“写优化”。而且数据结构太“严谨”，不断的”平衡“太繁琐，是个传统保守的结构。
2) skiplist
google的levelDB用的就是它，它的结构不“严谨”，“平衡”也比较随意，读写性能也不错，已经是一个不错的选择。但是他的cpu cache-efficiency不好，也不好控制。
下面说个有趣的数据结构：OMT
源码: https://github.com/shuttler/omt
由tokudb的人提出，全称是Order Maintenance Tree，它有着较好的cpu cache-efficiency，“平衡”性更随意和可控。它的性能也很出色，已超过我以前写的skiplist，且它操作起来很方便，除了支持普通的insert/find/delete外，还支find_next/find_previous/range操作,在范围最值查询上很有用途。
类似Cartesian tree: http://en.wikipedia.org/wiki/Cartesian_tree
整个tree的元素用一个数组表示，使具有父子关系的元素，在数组里尽量相邻存储，尽可能发挥cpu cache line的优势，也就是vEB layout，美帝叫这个为cache oblivious。（其实io-bound的优化也是基于这个小理论)。