总阅读量:次

⭐⭐⭐ Spring Boot 项目实战 ⭐⭐⭐ Spring Cloud 项目实战
《Dubbo 实现原理与源码解析 —— 精品合集》 《Netty 实现原理与源码解析 —— 精品合集》
《Spring 实现原理与源码解析 —— 精品合集》 《MyBatis 实现原理与源码解析 —— 精品合集》
《Spring MVC 实现原理与源码解析 —— 精品合集》 《数据库实体设计合集》
《Spring Boot 实现原理与源码解析 —— 精品合集》 《Java 面试题 + Java 学习指南》

摘要: 原创出处 jianshu.com/p/18b4bfde8c6c 「Mr林_月生」欢迎转载，保留摘要，谢谢！

🙂🙂🙂关注**微信公众号：【芋道源码】**有福利：

  1. RocketMQ / MyCAT / Sharding-JDBC 所有源码分析文章列表
  2. RocketMQ / MyCAT / Sharding-JDBC 中文注释源码 GitHub 地址
  3. 您对于源码的疑问每条留言都将得到认真回复。甚至不知道如何读源码也可以请教噢。
  4. 新的源码解析文章实时收到通知。每周更新一篇左右。
  5. 认真的源码交流微信群。

什么是索引？

当我们使用汉语字典查找某个字时，我们会先通过拼音目录查到那个字所在的页码，然后直接翻到字典的那一页，找到我们要查的字，通过拼音目录查找比我们拿起字典从头一页一页翻找要快的多，数据库索引也一样，索引就像书的目录，通过索引能极大提高数据查询的效率。

索引的实现方式

在数据库中，常见的索引实现方式有哈希表、有序数组、搜索树

  • 哈希表 哈希表是通过键值对（key-value）存储数据的索引实现方式，可以将哈希表想象成是一个数组，将索引通过哈希函数计算得到该行数据在数组中的位置，然后将数据存到数组中，容易发现一个问题，如果两个索引通过哈希函数计算后得到的数组位置相同要怎么办？在这里，数组的每个value都是一个链表，链表上的每个元素都是一个数据，新数据直接添加到链表尾部。

    哈希表.png

    所以数据库查询过程为：索引通过哈希函数计算数据所在位置--> 遍历指定位置的链表，找到满足条件的数据。

    要注意的是，链表上的数据元素不是有序的，每次有新数据加入时，新数据时直接添加到链表尾部，这样做的好处是添加数据时很方便。

    哈希表不擅长进行区间查询，一般都用于等值查询

    ​ 1、两个相邻索引通过hash函数后计算得到的数组位置不一定还保持相邻

    ​ 2、链表上的数据是无序的

  • 有序数组 顾名思义，有序数组是按索引大小将数据保存在一个数组上，因为该数组是有序的，可以通过二分法很容易查到位置，找到第一个位置后，通过向左/向右遍历很容易得到所求区间的数据。因此，无论是等值查询还是区间查询，效率都极高。 但缺陷也是显而易见的，当向数组中间n位置插入一条数据时，需将n后面的数据全部往后移动，所以，这种索引一般用于静态存储引擎。

  • 搜索树

二叉搜索树：一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 二叉搜索树的左、右子树也分别为二叉搜索树。 平衡二叉树：平衡二叉树是在二叉搜索树的基础上引入的，指的是结点的左子树和右子树的深度差不超过1. 多叉树：每个结点可以有多个子结点，子节点的大小从左到右依次递增。

当使用平衡二叉实现索引时，结构如下图

图片来自课程文章

从图中可发现，每次查询最多需要访问4个节点必能得到所要数据。例如查询user2时，查询过程为：userA-->userC-->userF-->user2。 所以查询速度很高，同时，因为搜索树的特性（左子树小于右子树），区间查询也很方便。

如果搜索树存于内存中，与多叉树相比，二叉树的搜索速率是最高的，但实际上数据库使用的是n叉树而不是二叉树。

1、索引不仅存于内存，还是写到磁盘上 2、搜索树上的每个结点在磁盘上表现为一个数据块 3、多叉树每个结点下可以有多个子节点，所以存储相同数据量时多叉树的树高比二叉树小，查询一个数据需要访问的结点数更少，即查询过程访问更少的数据块。查询速度较高。

innodb的索引模型

innodb使用B+树作为索引结构。 在B+树中，我们将节点分为叶子结点和非叶子结点，非叶子结点上保存的是索引，而且一个节点可以保存多个索引；数据全部存于叶子结点上,根据叶子结点的内容不同，innodb索引分为主键索引和非主键索引。非主键索引也称为二级索引。 主键索引的叶子结点中保存的数据为整行数据，而非主键索引叶子节点保存的是主键的值。

主键索引图

非主键索引图

通过主键索引查询数据时，我们只需查找主键索引树便可以获取数据；通过非主键索引查询数据时，我们先通过非主键索引树查找到主键值，然后再在主键索引树搜索一次，这个过程称为回表，也就是说非主键索引查询会比主键查询多搜索一棵树。所以我们应尽可能使用主键查询。

索引维护

添加新行时，将会在索引表上添加一条记录，如果是索引递增插入时，数据都是追加在当前最大索引之后，不会对树中其他数据造成影响；如果新加入的数据的索引值位于节点的中间，需要挪动部分节点的位置，从而保持索引树的有序性。 而且，相邻多个节点是存储在同一个数据页上的，此时，如果是在已经存储满状态的数据页中插入节点，会申请新的数据页，将部分数据挪动到新的数据页，这个过程称为页分裂，页分裂除了会影响性能，还会降低磁盘空间利用率。不规则数据插入时,会造成频繁的页分裂。

当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并

所以，一般情况下会采用递增主键，使新数据递增插入。

使用业务逻辑字段做主键有什么优缺点？

1、业务逻辑字段不容易保证索引树结点有序插入，这样写入成本较高。 2、innodb默认使用整数类型作为主键，主键长度较小，二级索引的叶子结点中保存的是主键值，主键长度越小，二级索引的叶子结点占用空间也就越小。 3、当然，使用业务逻辑字段做主键也有好处，可以避免回表，每次只需扫描一次主键索引树即可 综上，从性能和存储空间方面考量，自增主键往往是更合理的选择,当业务场景有且只有一个索引，而且该索引为唯一索引时，此时更适合使用业务逻辑字段作为主键。

因为数据修改/删除、页分裂等原因，会导致数据页空间利用率降低，此时，可以考虑重建索引，将数据按顺序插入，提高磁盘空间利用率。但重建主键索引和普通索引会有不同影响，重建普通索引，可以达到提高空间利用率的目的，且不会对其他索引造成影响，但如果重建主键索引就不合理了，会影响所有普通索引，性能影响较大，而且无论是新建/删除主键，都会重建整张表。这时我们可以使用alter table T engine=InnoDB这个语句代替。

查看索引利用率

查看performance_schema.table_io_waits_summary_by_index_usage表

文章目录
  1. 1. 什么是索引？
  2. 2. 索引的实现方式
  3. 3. innodb的索引模型
    1. 3.1. 索引维护