索引的本质#
- 索引是帮助MySQL高效获取数据的排好序的数据结构
- 索引数据结构
- 索引的建立就是数据排序的过程
为什么二叉树不适合做索引#
- 因为当数据在插入的数据，如果是排好序的，二叉树则会退化成链表，这样就失去了索引的意义。特别是自增主键，默认就是会建索引的。
为什么红黑树不适合做索引#
- 因为红黑树是弱平衡树，如果插入的数据是排好序的，则只会单边增长，查询效率依然不高效。特别是自增数据量大的时候，高度非常大。
为什么Hash表不适合做索引#
- 哈希表对于范围查找和排序效率低，但对于单个数据的查询效率很高。
B-Tree结构#
- 叶节点具有相同的深度，叶节点的指针为空
- 所有索引元素不重复
- 节点中的数据索引从左到右递增排列
B+Tree结构#
- 非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引
- 叶子节点包含所有索引字段
- 叶子节点用指针链接，提高区间访问性能；
MySQL 为什么使用 B+ 树来作索引#
- 由于mysql通常将数据存放在磁盘中，读取数据就会产生磁盘IO消耗。而B+树的非叶子节点中不保存数据，B树中非叶子节点会保存数据，通常一个节点大小会设置为磁盘页大小，这样B+树每个节点可放更多的key，B树则更少。这样就造成了，B树的高度会比B+树更高，从而会产生更多的磁盘IO消耗。
- B+树叶子节点构成链表，更利用范围查找和排序。而B树进行范围查找和排序则要对树进行递归遍历
B树与B+树比较#
- B+树层级更少，查找更快
- B+树查询速度稳定：由于B+树所有数据都存储在叶子节点，所以查询任意数据的次数都是树的高度h
- B+树有利于范围查找
- B+树全节点遍历更快：所有叶子节点构成链表，全节点扫描，只需遍历这个链表即可
- B树优点：如果在B树中查找的数据离根节点近，由于B树节点中保存有数据，那么这时查询速度比B+树快。
