引言
什么是索引？
答：是帮助MySQL高效获取数据的数据结构。
什么是全表扫描？
答：是将整张表扫描一遍，效率非常低。
本文言简意赅的总结索引的几种实现原理：
- hash算法
- 平衡二叉树（AVL树）
- B树实现
- B+树实现（MyISAM和InnoDB使用）
hash算法
原理：根据某一列（如userName）创建索引。
优点：查找可以根据key进行访问，效率非常高。
缺点：不能进行范围查询（因为无法比较大小）。
其它：映射函数叫散列函数，存放记录数组叫散列表。
平衡二叉树（AVL树）
原理：取一中间值，中间值左边称为作为左子树，右边称为右子树，左子树比中间值小，右子树比中间值大。
优点：使用的是折半查询，与二叉树查询相同，效率非常高。
缺点：支持范围查询，但是需要回旋。
B树
原理：可以知道平衡二叉树越高，IO次数越多，B树的出现就是为了减少二叉树的高度的。
优点：B树节点元素比平衡二叉树多，效率比平衡二叉树高。
缺点：范围查询需要回旋。
B+树
原理：集成B树，有叶子节点和非叶子节点，非叶子节点只包含Key，叶子节点包含key和value。
优点：B+树的出现就是为了解决范围查询问题，减少IO的操作，它继承了B树的特性，解决了回旋的问题。
缺点：因为冗余节点数据，比较占硬盘大小。
