MySQL索引

目录

1.索引

1.1 索引本质

1.2 索引的数据结构

1.3. 举例说明：

1.4. 二叉树

1.5. 红黑树

​编辑

1.6. B树 

 1.7. B+树

1.8. 为什么数据库索引选择b+树

1.9 hash索引

2. 存储引擎

2.1 MyISAM 

2.2 innodb 

2.3 聚集索引和非聚集索引 

2.4 为什么建议Innodb表必须建主键 

2.5 非主键索引

3. 联合索引

3.1 概括

3.2 底层结构​编辑

---

1.索引

1.1 索引本质

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

1.2 索引的数据结构

• 二叉树
• 红黑树
• Hash表
• B-Tree 

1.3. 举例说明：

数据存储的时候，插入数据，数据保存在磁盘中，当你插入第二条数据的时候，可能已经到了第二天了，磁盘存入数据是一个磁道一个磁道写入的，这段时间会进行其他数据的存储，当你插入第二条数据的时候就不会跟第一条数据挨着了，即数据表的数据在磁盘是随机分布的不一定挨着的

下图如果查找数据89的话，它需要在左边列表中一个一个对比，这个比对的话需要磁盘中拿出数据，进行比对，产生大量的磁盘io，所以需要控制查找次数

所以说我们把col2这列数据放入到一种数据结构中，比如下图中右边的二叉树，按照key-value的形式进行存储，二叉树的特点就是右边的数据比节点的数据小，左边的比节点数据大，这样的话如果查找89这个数据只需要查找两次，跟上面挨个查找6次相比，肯定效率更高

1.4. 二叉树

那为什么不用二叉树作为MySQL的索引数据结构呢，如果是连续的数据存储到二叉树中，会出现这样的现象

这样的话就跟链表没什么区别了，这样的话跟全表扫描没区别

总结：单边增长的数据，在二叉树中对查找效率没有提升

1.5. 红黑树

每次往里面添加的数据，都会做一次平衡，其实也是一颗二叉树，二叉平衡树，问题在于如果数据量特别大的话，它的树的高度会很高很高

1.6. B树 

相当于在磁盘空间分配稍微大一点，里面可以放更多的索引元素(原来就放一个)， 如下图一个大的节点里面放很多索引元素，里面这个小的节点是一个key-value，value就是索引所在行的磁盘文件地址，

• 叶节点具有相同的深度，叶节点的指针为空
• 所有索引元素不重复 节
• 点中的数据索引从左到右递增排列
• 没有叶节点的指针的话，范围查找效率会很慢，因为每次都需要从头节点依次向下找去比对

 1.7. B+树

B树的变种

• 非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引
• 叶子节点包含所有索引字段
• 叶子节点用指针连接，提高区间访问的性能

已经排好序放到b+树中

元素都放到非叶子节点里面去了

过程：

比如查找30这个元素，先从根节点去查找，把根节点所有元素都load到内存中，然后拿这个30到内存中去做比对，用高效的查找算法定位30应该在15-56之间，15-56这之间存储的就是15数据页在磁盘中的地址，说白了就是找到了下一个节点的起始位置(下一个磁盘的文件地址)，然后继续查找，然后定位到20-49之间，同样加载到内存，查找又定位到下一个磁盘文件地址，重复加载到内存进行比对，最终找到30这个节点，然后拉出这个磁盘文件地址，找出对应元素，叶子结点存储的信息应该就是磁盘地址，就是数据存储的真实地址，就是这条数据

你根据索引进行对比，你加的索引，就是把这个字段所有数据都排序好放到数据结构中，然后一一对比，最后找出磁盘的真实地址，拉出数据

下面那一行称为一页，这一页一次分配为16k，你一次性把所有数据都加载到内存中，会把内存撑爆，肯定不行

1.8. 为什么数据库索引选择b+树

影响索引的查找效率的因素，是树的高度，我们假设有2000万数据需要存储，用b树进行存放，单个节点能存放1kb数据，第一行可以存放16个节点 ，每个子节点也是可以放16个数据，以此类推，然后16的多少次方达到2000万，肯定是大于3的，相当于数据高度肯定会大于3

而b+树，叶子节点只存放索引元素，每一行都可以存放更多的索引元素

1.9 hash索引

如果某一列变为hash索引的话，会把这些数据做一次hash运算，定位出数据存储的位置，如果发生hash碰撞的话，就以链表的形式进行存储，如果查找某一个元素的话，对这个元素进行hash运算，定位之后对链表进行遍历，找到对应元素之后，相应也能找到元素的磁盘地址

问题：

• 很多时候Hash索引要比B+ 树索引更高效
• 仅能满足 “=”，“IN”，不支持范围查询，hash根本就没有比大小的概念，用不到索引的话，就全表扫描了，但是如果B+树进行范围查找的话，特点就是已经排好序的，而且可以根据指针拿到所有符合条件的远元素
• hash冲突问题 

2. 存储引擎

2.1 MyISAM 

 引擎一般来讲都是相对于表而言，上图是实际存储在磁盘中的数据，数据表结构相关信息的数据存放在frm文件中，MYD就是myisam+data表里面的数据，MYI就是myisam+index索引

上图过程：假设where col1 = 30，col1添加了索引，所有数据都会存放在b+树中，然后通过30从根节点去遍历，找到子节点对应的数据行，索引所在行的磁盘文件地址(换句话说，是通过这个元素在myi文件中，找到地址)，根据这个地址去myd文件中定位具体的数据，

2.2 innodb 

一样，也是表结构和表数据两个文件

子节点存放了索引所在行的所有数据，MyIsam存在的索引所在行的地址 

2.3 聚集索引和非聚集索引 

聚集索引：叶节点包含了完整的数据记录，查找速度快

非聚集索引：索引和数据分开存储的，需要在两个文件查找，速度会慢一点

innodb索引和数据都是在idb文件中，而MyIsam索引是在myi文件中，数据是在myd文件中

innodb只会有一个聚集索引，其他索引都是非聚集索引

2.4 为什么建议Innodb表必须建主键 

为什么建主键

因为innodb的索引和数据存储在一起的，所以如果你没有定义索引，该如何存储数据呢，innodb会找一列数据都不相等，作为索引组织B+树，如果选不到的话，mysql会建一个隐藏列，去维护一个唯一的id，来组织整张表的数据，如果我们不建主键的话，还需要mysql自己去找，自己去建，增加很多mysql工作

主键为什么整型

你每次查找数据都是进行一一比较，如果你是uuid(是字符串)作为主键，效率比较低，位数太长了，可能影响性能不大，而且太长了的话，也会占用一部分空间，建议用整型  

自增

因为b+树每次添加的时候都是按照顺序进行存放的，就是你放是无序的，但是存的时候是有顺序的，如果不是自增的话， 会向已经排好序的数据中添加数据，可能会造成非叶子节点进行分裂，还可能导致树做平衡，相比于自增的话，效率会低一点

2.5 非主键索引

为什么非主键索引结构叶子节点存储的是主键值

如果是普通索引的话，存放的就不是数据了，一般是主键数据，一个是为了节约存储空间，如果这张表有好几个索引，那么每个数据都要存放好几遍，很浪费空间，主要就是节约存储空间

第二个就是一致性，如果主键索引和普通索引都需要维护表的数据的话，就涉及到两个表都插入成功了才算插入成功，其实可以先插入主键索引的那个表，然后根据主键索引的数据再次插入另外索引的那个表里面，这样的话就是比较复杂了

3. 联合索引

3.1 概括

定义：多个字段共同组织成一个索引

作用：主要就是如果有多个单值索引的话，要尽量用2-3个多值索引代替

3.2 底层结构

也是B+树结构，例如上图，按照复合索引先后顺序，数据排序好维护在b+树中，先按照name、age、position顺序来进行排列，如果第一个字段就能够排出顺序，后面字段就不需要进行判断了，如果第一个字段相同的话，依次比较下一个字段的大小进行排序(上图是联合主键，最下面那个不是主键，而是另一个字段的值)。

冗余索引的建立：每一页最小的进行提取作为节点

最左前缀原理：就是必须要用到第一个索引，即最左边的索引，要不然就会索引失效，如果你直接按照第二个字段去查找数据的话，是无法按照第二个字段索引去查找的，因为复合索引是先按照第一个字段进行排序，如果第一个字段排序相同的话，才按照第二个字段去排序的，你直接按照第二个字段去查找的话，它还是无序的，所以索引会失效