二叉树

典型的索引譬如在内存中维护一个二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针，这样就可以运用二叉查找在 O(log2n) 的复杂度内获取到相应数据。

左侧为数据记录的物理地址，右侧为查找树，需要注意的是，逻辑上相邻的记录在磁盘上也并不是一定物理相邻的。

二叉树在极端情况下会变成线性结构，也就是每个节点都只有左子节点或者只有右子节点，这样就无法利用二分查找只能从第一个节点开始向后遍历了，所以为了维持　 O(log(N))　的时间复杂度，我们需要在插入节点的时候对节点进行调整以保证树的平衡，所以平衡二叉树插入的时间复杂度也是　 O(log(N))　，二叉树只有两个子节点，如果数据量很大则树就很高，树的每一层一般不在同一个数据块中存储，为了尽量的减少磁盘读写次数，我们用Ｎ叉树来代替二叉树，在 MySQL 中这个Ｎ一般为　 1200，这样树高是　４　的话也可以存储亿级别的数据，而且树的前面两层一般都在内存中，MySQL 中用到的　Ｂ＋　树，一般用非叶子节点构建索引，而叶子节点用来存储具体的值。