mysql为什么用B+树做索引

本文主要是介绍mysql为什么用B+树做索引，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

为什么不用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+树
结构图

中序遍历

检索原理