Mysql索引底层数据结构

索引是帮助MySQL高效获取数据的排好序的数据结构

接下来我们会对这句话进行一步步的剖析

索引数据结构
- 二叉树
  
  二叉树虽然会提高查询性能，但是在其插入的元素呈递增的情况下，二叉树就会退化成一个链表，从而降低了搜索的性能。
- 红黑树
  
  使用红黑树虽然没有了上述二叉树在递增添加元素时候退化成链表的情况，但是红黑树却存在一个问题，即：使用红黑树的时候，不断往红黑树上添加节点，就会使红黑树的高度不断的变高，我们尝试想，如果我们往红黑树里添加几百万节点的时候我们的高度会有多高，所以MySQL索引也不采用这种数据结构。
  
  关于红黑树的特性，有不了解的小伙伴可以看我的这篇博客：
  
  https://www.cnblogs.com/coderD/p/14612349.html
- 哈希表
  
  这里我先把我自己有关哈希表的详细博客贴在下边
  
  https://www.cnblogs.com/coderD/p/14673913.html
  
  接下来，我们开始进入主题：
  - 对索引的Key进行一次hash计算就可以定位出数据存储的位置
  - 其实很多时候Hash索引要比B+树效率高
  - 仅能满足“=”，“IN”，不支持范围查询
  - 哈希表存在哈希冲突
  如上图，如果计算Alice和Jim的哈希值相等的时候，就会用单向链表串联起来，同时当不断添加元素的时候，单向链表就会变为红黑树。
- B树
  - 叶节点具有相同的深度，叶节点的指针为空
  - 所有索引元素不重复
  - 节点的数据索引从左至右递增排列
  如下图所示：
  
  每个节点都有一个data域，指向磁盘中的数据。
  
  我们仔细看就会发现每层的节点从左到右倒是递增的。
- B+树（B树的变种）
  - 非叶子节点不存储data，只存储索引（冗余），可以放更多的索引
  - 叶子节点包含所有的索引字段
  - 叶子节点用指针连接，提高区间访问的性能

所以，综上所述，MySQL底层索引的数据结构是B+树，同时我们也理解了一开始我们说的话，索引是帮助MySQL高效获取数据的排好序的数据结构。

非聚集索引和聚集索引

MyISAM索引文件和数据文件是分离的(非聚集)

非聚集索引的解释如下：

因为它是一颗B+树，所以只有在叶子节点才会有一个data域，用来指向硬盘上的存储地址，像这样的还得回表去查找的就为非聚集索引。
InnoDB索引实现(聚集)

聚集索引与非聚集索引相反，它是在叶子节点就存储了所有的信息，在查找到对应的Id值以后，就不需要在回表操作了。
- 表数据文件本身就是按B+Tree组织的一个索引结构文件
- 聚集索引-叶节点包含了完整的数据记录
- 为什么建议InnoDB表必须建主键，并且推荐使用整型的自增主键？
  - 为什么建议InnoDB表必须建主键？
    
    如果你不建主键的话，MySQL就会选择一个没有重复的字段作为主键，如果没有找到的话，就会建立一个隐藏主键，但是这些工作我们自己做不是更好？为什么要劳苦MySQL帮我们去做呢？
  - 为什么要使用整型？
    
    因为如果我们用字符串作为索引的话，事实上我们比较字符串就是比较一位一位的去比较他们的ASCII值，这样就会降低性能。
  - 为什么要自增？
    
    我们看B+树上的每层节点都是从左到右依次递增的，如果不是递增的话，它就会不断的调整数据的物理地址，分页，同样会降低性能。
- 为什么非主键索引结构叶子节点存储的是主键值？(一致性和节省存储空间)
  - 保持一致性：
    
    因为对数据表进行操作的时候，同一行记录的页地址会发生变化，而非主键索引结构保存的是主键的值，无需进行修改
  - 节省存储空间
    
    非主键索引只保存主键是为了节省空间。