索引Core

Q：索引数据结构为什么不使用二叉树？
A：二叉树虽然是搜索效率最高的，但是索引不止存在内存中，还要写到磁盘上。当数据量大的时候，即节点很多（二叉树每个节点仅有两个儿子），也就导致树的高度就增加。当查询的数据位于叶子节点的时候，磁盘随机读次数（树的层数）自然会很多，那本次查询就会相当慢了。
注：MySql默认一个节点的长度为16K，一个bigint长整数字段索引的长度为 8B，另外每个索引还跟着6B的指向其子树的指针，所以每个节点能挂着16K/14B ≈ 1170个儿子。