数据库索引原理

1.为什么需要索引

索引就相当于一本书中的目录，如果要找其中的某一部分内容，可以先确定大概在那一章哪一节，这样就不需要从书籍第一页开始去找（全表扫描）。

索引可以有多个，像新华字典有按拼音，部首，笔画查找方式，对应不同的索引

按拼音

按笔画

按部首

2.索引的原理

以MySQL索引为例

2.1 索引实现数据结构

二叉树

特点：左子树小于根节点键值，右子树大于根节点键值

概念：

1. 键值：表中记录的主键/索引值
2. 指针：存储子节点的地址信息
3. 数据：记录表中主键的数据

表的主键为id，指针存储每行记录存储的磁盘地址，数据对应每行的存储的数据

B树（平衡多路查找树）

缺点：

（1）每个节点都有key，同时也包括data，而每个页存储空间是有限的，如果data比较大的话，就会导致每个节点存储的key数量变小; （2）当存储的数据量很大的时候，会导致深度较大，增加查询时磁盘io次数，进而影响查询性能;

（3）无法做范围查询

B+树

B+树和B树的区别：

1.非叶子节点只存储键值信息（非叶子节点只做索引功能，这样就可以在非叶子节点上大大增加键值）

2.所有叶子节点间都有链指针连接（有序链表，在查大小区间的数据时更方便）

3.数据全部存在叶子节点中（所以每次查找的次数不一样，而B树则有可能在第一次io的时候查找到数据，所以查询比较稳定）;

4.支持范围查询，因为叶子节点每页存储指向下一页的地址，链表结构

Hash函数

public static void main(String[] args) {

      System.out.println("张飞".hashCode());
      System.out.println("关羽".hashCode());
}

public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

结果：

张飞 => 794046

关羽=> 679082

优点：

采用 Hash 进行检索效率非常高，基本上一次检索就可以找到数据，而 B+ 树需要自顶向下依次查找，多次访问节点才能找到数据，中间需要多次 I/O 操作，从效率来说 Hash 比 B+ 树更快。

缺点：只适合做等值查询 where a=10

1. Hash 索引不能进行范围查询，而 B+ 树可以。
2. Hash 索引不支持联合索引的最左侧原则（即联合索引的部分索引无法使用）
3. Hash 索引不支持 ORDER BY 排序，因为 Hash 索引指向的数据是无序的，因此无法起到排序优化的作用，而 B+ 树索引数据是有序的，可以起到对该字段 ORDER BY 排序优化的作用。
4. 无法用 Hash 索引进行模糊查询，而 B+ 树使用 LIKE 进行模糊查询的时候，LIKE 后面前模糊查询（比如 % 开头）的话就可以起到优化作用。

2.2 Innodb页底层结构

分成三个部分

1. 页头：包含前后页的指针
2. 页目录：包含数据区（分组）的最小id值，方便通过指针查询到数据
3. 数据区：用于存放数据，指针依次向下

为什么要引入页目录？

比如：我要查询id为4的数据，需要从上到下查询4次。把数据区的数据分组，页目录存储每组数据最小的id值。那么我只需要通过目录3，查询2次即可。提高了查询效率。

当一页存满之后，数据会存放到下一页，通过双向指针连接，如图：

B和B+树具体生成过程可以通过网站熟悉

https://www.cs.usfca.edu/~galles/visualization/BTree.html ----B树

https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html ----B+树

2.3 MySQL的索引类型

聚簇索引

聚簇索引（Clustered Index）一般指的是主键索引（没有主键就使用唯一索引或者系统自动隐藏新建的键)，聚簇索引也被称之为聚集索引，聚簇索引只有一个

非聚簇索引

非聚簇索引在 InnoDB 引擎中，也叫二级索引，除了聚簇索引外的索引是非聚簇索引，非聚簇索引可以有多个，非聚簇索引不存放data数据，叶子节点存放的是聚簇索引的值。

索引在 InnoDB 中是使用 B+ 树实现的，比如我们创建一张 student 表，它的构建 SQL 如下：

drop table if exists student;
create table student(id int primary key,name varchar(16),class_id int not null,index (class_id) )engine=InnoDB;
insert into student(id,name,class_id) values(1,'张三',100),(2,'李四',200),(3,'王五',300);

以上 student 表中有一个聚簇索引（也就是主键索引）id，和一个非聚簇索引 class_id。

非聚簇索引 class_id对应的B+树如下图所示：

class_id 索引结构

聚簇索引 id 对应的 B+ 树如下图所示：

id主键索引结构

另一种分类：

普通索引（单个字段）: index(id)

主键索引: primary key（不为空且唯一）

唯一索引: unique index（唯一）

联合索引(组合索引)

primary key(id,name): 联合主键索引

unique index(id,name): 联合唯一索引

index(id,name): 联合普通索引

全文索引: fulltext index(note) 用于搜索很长一篇文章的时候，效果比较好。

说明: 最好还是用全文搜索服务Elasticsearch、solr来解决。

与聚簇索引和非聚簇索引的关联

聚簇索引:默认使用主键索引，如果没有主键，使用唯一索引，如果没有唯一索引，使用隐藏的主键索引

2.4 MySQL带索引查询过程

如果要查询class_id=300的数据，则查找过程如下：

1.先从class_id 非聚簇索引树中查找，根节点是200，,300>200，则查找右子树；

2.右子树查找，有200和300，遍历查找到300，class_id=300对应的主键id为3；

3.从id主键索引树中查找id=3的数据，过程和1-2步骤类似，查找到对应的数据

3. 性能优化实践

3.1 执行计划

作用:

• 可以知道SQL语句的执行顺序。
• 可以知道SQL查询语句是否命中索引。
• 可以分析查询语句或表结构的性能瓶颈。

执行顺序：

id不同的由大到小执行，相同的由上到下执行

是否命中索引

3.2 哪些字段适合建立索引

drop table if exists student; 
create table student(id int primary key,name varchar(16),class_id int not null,sex varchar(2) not null, index (class_id),index(name), index(sex))engine=InnoDB;
insert into student(id,name,class_id,sex) values(1,'张三',100,'男'),(2,'李四',200,'男'),(3,'王五',300,'女');

sex字段只有男和女两种值，适合建立索引吗？

select * from student where sex='男';</pre>

如果这个表数据有1万条（id从1到10000），男和女各5000条（男的为id奇数，女生为id偶数），这个语句执行过程：

sex索引

主键索引

步骤1：先从sex索引查找sex='男'的id数据,得到的数据为1,3,5,7,9,11,....共5000个；

步骤2：使用步骤1得到的数据从主键索引回表查询，相当于

select * from student where id in(1,3,5,7,9,11,....)</pre>

因为id的值太多，需要的io的次数是5000次左右，而且这个io是属于随机io，速度慢；而如果采用全表扫描，因为同一个表数据在磁盘中存储在一块的，所以是顺序io，速度比随机io快得多，所以这种情况下总的耗时通过索引查找可能会比全表更慢。

select count(distinct(field))/count(*) from table</pre>

这个值越大越好，唯一索引或者主键这个值是1。

3.3 覆盖索引

定义:通过索引值可以直接找到要查询字段的值，而不需要通过主键值回表查询，那么就叫覆盖索引

select * from student where class_id=300;

因为class_id索引只有class_id和id，如果查询语句为：

select id,class_id from student where class_id=300;

这个语句所有字段在索引中就可以找到，不需要从主键索引回表查询。

select id,class_id,name from student where class_id=300;

如果使用 class_id索引，就需要回表，如果索引包含所有字段，则可以通过覆盖索引。

index(class_id, name) 建立组合索引，就可以避免回表查询

3.4 索引下推

索引：index(name,age)

select * from tuser where name like '张%' and age=10;

如果没有用索引下推

使用下推

3.5 前缀索引

name字段后缀基本相同，这种情况建立索引时不需要将整个字段做索引，可以将前面N个字符索引，例如例如这个例子可以将name前3个字符做索引 index(name(3))

优点：

1.减少了索引的存储空间；

2.加快检索的效率

3.6 避免索引失效

1.使用!= 或者 <> 导致索引失效

2.类型不一致导致的索引失效

3.函数导致的索引失效

4.运算符导致的索引失效

5.OR引起的索引失效

OR 导致索引是在特定情况下的，并不是所有的 OR 都是使索引失效，如果 OR 连接的是同一个字段，那么索引不会失效，反之索引失效。

6.模糊搜索导致的索引失效

7.NOT IN、NOT EXISTS导致索引失效

8.IS NULL走索引，IS NOT NULL不走索引 [图片上传失败...(image-3152e5-1674029814626)]

根据这个情况，建议大家这设计字段的时候，如果没有必要的要求必须为 NULL ，那么最好给个默认值空字符串，这可以解决很多后续的麻烦。

4.PG和MySQL索引不同点

1.PG的索引实现方式除了B+树，还有其他方式

后面分享会进行研究这些索引的不同

2.PG支持部分索引(条件索引)

现实例子中，常会碰到键值分布不均匀的属性，如表test一个名为FLAG的属性，有A、B、C三个值，其中值为A的记录占95%，值为B的占3%，C占2%。在FLAG上建立索引，搜索FLAG=‘B’或‘C’可利用到此索引，而搜索FLAG=‘A’则因有大量的重复值而利用不到此索引。也就是说此索引有95%的内容是无效的，白白浪费了存储等资源。

PostgreSQL有种索引，叫Partial Index(部分索引)可以很好的解决以上问题， 它是在表的纵向子集上建立索引，可以认为是带where表达式的索引。
如以上例子，我们在FLAG上建立部分索引flag_index：
create index flag_index on test ( flag ) where flag='B' or flag='C'
这个索引只包含B和C值，不包含A值，大大减少了存储空间，提高了运行效率。

只有匹配where 表达式的查询语句才可利用到此部分索引，如查询语句
select ...where flag='B' 。。。。可利用到索引
select ...where flag='C' 。。。。可利用到索引
select ...where flag='A' 。。。。利用不到索引。

再举一种场景：

select * from table where field1 !='111' and field2 like '%23443';

虽然这个表有索引field1和field2，但是没有生效，如果这个条件是比较固定的，大部分场景就是这个查询条件，那么可以用这个条件建立部分索引。

create index condition_index on table ( field1,field2 ) where field1 !='111' and field2 like '%23443';

这种查询在MySQL基本上是不太好优化的 。

参考文章

1.https://blog.csdn.net/sumengnan/article/details/112796692

2.https://blog.csdn.net/DarzenWong/article/details/122668926