Mysql索引的探索

1 索引的本质

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

• 现在假设索引的数据结构是查找二叉树结构，如上图的表结构，索引字段是col2，构建查找二叉树就是右边的结构，eg:
• 现在有一条sql语句，select * from t where t.col2 = 89;
• 执行的流程是先查找二叉树，找到89这个节点(节点是一个<k,v>存储的结构，k是索引值89,v是这个索引所在行的磁盘存储指针0x77)。
• 根据v的磁盘存储指针，进行一次磁盘io操作就可以得到数据了。

注意

• 但是如果我们没有索引的话，就的按顺序遍历一条进行一次磁盘io,效率太低，当数据量大的话，就不可能的。
• 当索引是二叉树的结构的话，会存在什么问题呢？
  还是上面的例子，当我们的索引是col1字段的时候，这个时候构建查找二叉树的结构就是下面的样子，变成一条链表结构了。
  
  类似上面的结构，效率太低，每查找一个数据，都要在内存中从头遍历一遍。所以索引二叉树不可行的。

1.1 红黑树做索引呢？

• 红黑树的特点：
  • 根节点是黑节点；
  • 一个红节点，对应的子节点全是黑节点；
  • 叶子节点全是黑节点，为NUll;
  • 任意非叶子节点到叶子节点的路径上黑节点的数量一样；
• 红黑树作为一种平衡二叉树，但是不同于AVL树，红黑树通过改变节点路径之间的颜色变化，索引不会出现一条路径是其他路径的2倍长的，相比于AVL树，它的自旋转平衡的频次减少很多，在性能上比AVL树更优。
• 现在还是上面的例子，以col1字段为索引，构建红黑树：
  
  作为mysql的索引的话，存在问题就是当表里面是千万级的数据，那么导致红黑树的深度太深，查询太慢。在
  在看看利用col1构建AVL树的样子 ：
  
  AVL树在构建(1-7)的时候自旋4次，但是红黑树自旋是3次，索引红黑树性能更优。

1.2 mysql底层的索引是B+Tree结构：

• 先讲一下B-Tree结构：
  
  特点：多叉树，其中叶子节点的深度相同，叶子节点之间没有指针；
  所有的索引元素不重复，从左往右是自增排序的。
  并且每一个索引元素所在的位置上面保存着索引数据的磁盘文件指针；
• B+Tree结构：
  

1.3 mysql存储引擎MyisAM

• 这个存储引擎的表落到磁盘上面对应的文件是三个: xx.frm xx.MYI, xx.MYD
• xx.frm存储的是表结构相关的数据;
• xx.MYI存储的是索引数据;
• xx.MYD存储的是表的数据;
  
  上面的图是MyisAm的索引存储结构，索引和数据是分离的。

1.4 InnoDB的存储引擎

索引和数据在一起的。
在磁盘上对应的文件是:xx.frm 表结构的信息
xx.ibd 存储数据和索引
叶子节点存储了完整的数据，减少了回表的操作。
为什么innodb的主键推荐自增？因为底层数据存储按照主键来组织的，你不加主键的话，mysql会默认添加的主键的。整数型索引比较大小比UUID更效率跟高。
自增是因为 b+tree叶子节点之间具有双向指针的，方便范围查找来检索数据。
hash类型的索引解决不了的访问查找的。所以就是不行的。