为什么不用hash，二叉树，平衡二叉树（AVL），B-树呢？InnoDB并不支持hash索引
- 1.hash的时间复杂度是O(1)，但是会退化为O(n)，而且无法解决排序，范围查询等问题;
- 2.树的时间复杂度是O(log2(n));比O(n)小，所以排除hash；
- 3.二叉树的特点是
- 4.二叉树会产生的问题（由于不平衡，所以会右倾或者左倾，又退化成链表，复杂度从O(log2(n))变成O(n)）
- 5.平衡二叉树确实可以减少查询次数，但是当数据量很大，那么树高就会很高（磁盘IO就很大），也是不利于查找的；那么可以通过减少树的高度，变成矮胖树，来减少磁盘IO；
- ６.B树又叫二三树（B树比平衡二叉树减少一次IO）；
InnoDB默认磁盘页是16KB
B树检索原理 - 7.B+树
结构图
中序遍历
检索原理
B+树相对于B树有几点不同呢？
- 1.非叶子节点只存储键值信息；
- 2.所有叶子节点都有一个链指针；
- 3.数据记录都放在叶子节点中；