深入理解Mysql索引底层数据结构与算法

• 索引的概念：索引是帮助MYSQL高效获取数据排好序的数据结构
• 索引数据结构：
  • 二叉树
  • 红黑树
  • （B-Tree）B树
  • （B+Tree）B+树

因为数据的存储是在磁盘的不一定相连的一块区域上，所以每一次从磁盘上读取数据都需要进行一个I/O操作，然而I/O操作是需要性能开销及时间开销的，所以想提高sql的查询性能则需要尽量的减少I/O操作，则尽量的减少从磁盘中读取数据

1. 二叉树：

   • 每个节点上都会存储数据及磁盘的地址
   • 根节点的左边子节点永远小于右边子节点
   • 检索一个数据的时候，从根节点开始进行比较，如果大于当前节点则继续与右边节点比较，同理则与左边子节进行比较
   • 当数据量很大的时候二叉树的高度就会很高，每一次对比都需要从磁盘中读取数据，所以二叉树还是不太理想的
     

2. 红黑树（平衡二叉树）：

   • 每个节点存储值与磁盘地址
   • 不能有两个连续的红色节点（当出现连续的红色节点的时候，发生左旋或者右旋，把树平衡起来）
   • 相比二叉树，红黑树在查询速率上有了很大的进步，但是数据量一大I/O操作的频率还是太高

3. BTree（B树）

   • 每个节点存储值与磁盘地址
   • 在内存中划分出一块相对较大的区域，mysql中这片区域默认是大小16k，不再是一个主节点（索引数据的时候，以中位数据算法快速找出需要检索的数据）
   • 叶节点具有相同的深度，叶节点的指针为空
   • 所有索引元素不重复
   • 节点中的数据索引从左到右递增排列
     

4. B+Tree（B+树）：BTree的升级，BTree有的特性B+Tree也有

   • 相对BTree，B+Tree在非叶子节点中不再存储data(磁盘地址)，只存放索引（即冗余索引），可以存放更多的索引
   • 叶子节点包含了所有索引字段（即聚集索引）
   • 叶子节点之间用指针链接，提高了区间访问的性能（在范围查询，in，>，<等）
   • mysql用的是优化后的B+Tree，增加了从右到左的指针
     

5. Hash 数据结构

   • 对索引的key进行一次hash计算就可以定位出数据存储的位置
   • 很多时候Hash索引要比B+ 树索引更高效
   • 仅能满足 “=”，“IN”，不支持范围查询
   • hash冲突问题
     

mysql的存储方式比较，MyISAM，InnoDB

MyISAM

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

InnoDB

• 表数据文件本身就是按B+Tree组织的一个索引结构文件
• 聚集索引-叶节点包含了完整的数据记录
• 为什么建议InnoDB表必须建主键，并且推荐使用整型的自增主键？
  • 必须建立主键是为了防止mysql自动给表新增主键而带来的资源消耗：如果没有主键，innoDB会选择一个没有null值的唯一索引作为主键索引，如果没有唯一索引，则会创建隐含的rowid（随行记录的写入递增）作为隐含的聚集索引。
  • 选择自增主键时：每一次插入记录会顺序添加到索引的末端，自动有序，一页满了自动开启下一页
  • 如果使用非自增主键（uuid等）：由于每次插入主键的值近似于随机，因此每次新纪录都要被插到现有索引页得中间某个位置，此时MySQL不得不为了将新记录插到合适位置而移动数据，甚至目标页面可能已经被回写到磁盘上而从缓存中清掉，此时又要从磁盘上读回来，这增加了很多开销，同时频繁的移动、分页操作造成了大量的碎片，得到了不够紧凑的索引结构，后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。
• 为什么非主键索引结构叶子节点存储的是主键值？(一致性和节省存储空间)
  • 一致性：如果非主键索引结构叶子节点都存储所有的列数据，那么每一次修改则需要修改多次，只要有一次出错就破坏了一致性
  • 省存储空间：如果非主键索引结构叶子节点都存储所有的列数据，数据量一大则会占用很多的磁盘空间
    
    

• 联合索引