开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 2021-11-14 -> 正文阅读

[数据结构与算法]2021-11-14

1、索引介绍

1.1、什么是索引？

索引是数据结构，可以高效地获取数据
索引存储在文件系统中
索引的文件存储形式与存储引擎有关
索引文件结构
hash
二叉树
B树
B+树 （MySql索引文件结构）

1.2、索引的优势和劣势

优势：

可以提高数据检索的效率，降低数据库的IO成本，类似于书的目录。
通过索引列对数据进行排序，降低数据排序的成本，降低了CPU的消耗。
被索引的列会自动进行排序，包括【单列索引】和【组合索引】，只是组合索引的排序要复杂一些。
如果按照索引列的顺序进行排序，对应order by语句来说，效率就会提高很多.

劣势：
- 索引会占据磁盘空间
- 索引虽然会提高查询效率，但是会降低更新表的效率。比如每次对表进行增删改操作，MySQL不仅要保存数据，还有保存或者更新对应的索引文件。

1.3、索引分类

主键索引

主键是一种唯一性索引，它必须指定为PRIMARY KEY，不能为空，每个表只能有一个主键

一个主键并非一定只有一个列，也可以是多个列组成的联合主键

MySql会自动为主键创建索引

唯一索引

索引列的所有值都只能出现一次，即必须唯一，值可以为空；一张表可以在不同的字段建多个唯一索引

（另：主键索引与唯一索引的区别：

1. 主键是一种约束，唯一索引是一种索引，两者在本质上是不同的。

2. 主键创建后一定包含一个唯一性索引，唯一性索引并不一定就是主键。

3. 唯一性索引列允许空值，而主键列不允许为空值。

4. 主键索引在创建时，已经默认为非空值+ 唯一索引了。

5. 一个表最多只能创建一个主键索引，但可以创建多个唯一索引。

6. 主键更适合那些不容易更改的唯一标识，如自动递增列、身份证号等。

       7. 主键可以被其他表引用为外键，而唯一索引不能。）

普通索引

基本的索引类型，值可以为空，没有唯一性的限制
全文索引（用的很少）

全文索引的索引类型为FULLTEXT。全文索引可以在varchar、char、text类型的列上创建
组合索引

多列值组成一个索引，专门用于组合搜索

又称：复合索引、联合索引
空间索引

MySQL在5.7之后的版本支持了空间索引，而且支持OpenGIS几何数据模型。MySQL在空间索引这方面遵循OpenGIS几何数据模型规则。
前缀索引

在文本类型如CHAR,VARCHAR,TEXT类列上创建索引时，可以指定索引列的长度，但是数值类型不能指定。

1.3.2索引的CURD

创建索引

1：直接创建索引：

CREATE INDEX index_name ON table(column(length));  创建普通索引
CREATE UNIQUE INDEX indexName ON table(column(length)); 创建唯一索引
CREATE FULLTEXT INDEX index_content ON article(content); 全文索引

2：修改表结构的方式添加索引：

ALTER TABLE 表名 ADD 索引类型 (unique,primary key,fulltext,index)[索引名](字段名)

删除索引:

DROP INDEX index_name ON table;

查看索引：

show index from table_name;

更改索引

直接删除

1.4索引优化

1.4.1 Explain优化查询检测

EXPLAIN可以帮助开发人员分析SQL问题，explain显示了mysql如何使用索引来处理select语句以及连接表，可以帮助选择更好的索引和写出更优化的查询语句。使用方法，在select语句前加上Explain就可以了;

在这里插入图片描述

EXPLAIN能干嘛

可以查看以下信息

- id：表的读取顺序
- select_type：数据读取操作的操作类型
- possible_keys：哪些索引可以使用
- key：哪些索引被实际使用
- ref：表之间的引用
- rows：每张表有多少行被优化器查询
  
  详细字段可参考：https://www.yuque.com/cessstudy/mysql/mr224a#v7XWR

1.4.2 常见名词

案例表

id(主键) name(普通索引) age
1 哈哈 6
2 呜呜 3
3 呼呼 8

（1）回表

如果创建的索引是其它字段(普通索引，不是主键)，那么在叶子节点中存储的是该记录的主键(不是数据)，然后再通过主键去主键索引表查找对应的记录

经过了两个表的查询：

普通索引表：查到主键
主键索引表：查询记录数据
-- name是普通索引，在普通索引表中存储的是主键id的值，即1
-- 要想得到记录的值，需经过二次查询
select * from table where name="呜呜"

（2）索引覆盖

-- 一次查询就可以得到结果，不需要回表
select id from table where name= "哈哈"
根据name的值去name的B+树检索对应的记录，能获取到id的属性值，索引的叶子结点中包含了查询的所有列，此时不需要回表，这个额过程叫做索引覆盖，会有using index的提示，推荐使用
在某些场景中，可以考虑将要查询的所有列都变成组合索引 ，此时会使用索引覆盖（不会回表），加快查询效率。

（3）最左匹配

索引可以简单如一个列 (a)，也可以复杂如多个列 (a,b,c,d)，即联合索引。
如果是联合索引，那么key也由多个列组成，同时，索引只能用于查找key是否存在（相等），遇到范围查询 (>、<、between、like左匹配)等就不能进一步匹配了，后续退化为线性查找。
因此，列的排列顺序决定了可命中索引的列数。

例子：
如有索引 (a,b,c,d)，查询条件 a=1 and b=2 and c>3 and d=4，则会在每个节点依次命中a、b、c，无法命中d。(c已经是范围查询了，d肯定是排不了序了)

(4)索引下推

把原来在server层进行的条件过滤下推到存储引擎层，索引下推是默认开启的
select * from user where name = "呼呼" and age = "8";
没有索引下推前

先根据 name 从存储引擎中拉取数据到 server 层，然后在 server 层中对 age 进行数据过滤

有索引下推后

根据 name 和 age，直接在存储引擎中做数据过滤，把结果返给 server 层

可以减少返给 server 层的数据量

(5)前缀索引

如果索引列长度过长，这种列索引时将会产生很大的索引文件，不便于操作，可以使用前缀索引方式进行索引；前缀索引应该控制在一个合适的点，控制在0.31黄金值即可（大于这个值就可以创建）。

-- 这个值大于0.31就可以创建前缀索引，Distinct去重复
SELECT COUNT(DISTINCT(LEFT(title,10)))/COUNT(*) FROM Arctic; 

-- 增加前缀索引SQL，将人名的索引建立在10，这样可以减少索引文件大小，加快索引查询速度
ALTER TABLE user ADD INDEX `uname`(title(10));

1.5、优化小细节

当使用索引列进行查询的时候，尽量不要使用表达式，把计算逻辑放到业务层，减轻数据库运算压力
尽量使用主键查询，而不是其它索引，因为主键索引不会触发回表查询
如果索引列长度过长，可以使用前缀索引，否则会产生很大的索引文件，不便于操作
使用索引扫描来排序

参考：https://www.cnblogs.com/YC-L/p/14461561.html
- mysql有两种方式可以生成有序的结果：通过 排序操作 或者 按索引顺序扫描
  - 如果explain出来的type列的值为index,则说明mysql使用了索引扫描来做排序
  - 扫描索引本身是很快的，因为只需要从一条索引记录移动到紧接着的下一条记录
  - 但如果索引不能覆盖查询所需的全部列，那么就不得不每扫描一条索引记录就得回表查询一次对应的行
  - 这基本都是随机IO，因此按索引顺序读取数据的速度通常要比顺序地全表扫描慢
  mysql可以使用同一个索引即满足排序，又用于查找行，如果可能的话，设计索引时应该尽可能地同时满足这两种任务
  - 只有当索引的列顺序和order by子句的顺序完全一致，并且所有列的排序方式都一样时，mysql才能够使用索引来对结果进行排序
  - 如果查询需要关联多张表，则只有当order by子句引用的字段全部为第一张表时，才能使用索引做排序
  - order by子句和查找型查询的限制是一样的，需要满足索引的最左前缀的要求
  否则，mysql都需要执行顺序操作，而无法利用索引排序
union all，in，or 都可以使用索引
- 对于 索引列 最好使用 union all
  
  因为复杂的查询【包含运算等】将使 or、in 放弃索引而全表扫描，除非确定 or、in 会使用索引
- 对于 非索引字段 用 or 或者 in，因为要全表扫描，而 union all 会成倍增加表扫描的次数
- 对于既有 索引字段【索引字段有效】又包含 非索引字段，使用三者都可以，推荐使用 or、in
  
  参考：
  
  博客园：https://www.cnblogs.com/maohuidong/p/10478356.html
范围列可以用到索引
- 范围条件是：<、<=、>、>=、between
- 范围列可以用到索引，但是范围列后面的列无法用到索引，索引最多用于一个范围列

强制类型转换会全表扫描

-- 数据库中的电话号码是  字符串形式(varchar)，并建立了索引

-- 全表扫描，不会触发索引；因为以 数值 的形式查询，强制进行了类型转换
 select * from user where phone = 10086;

-- 触发了索引，不会全表扫描
 select * from user where phone = "1008698";

更新频繁，数据区分度不高的字段，不宜建立索引
创建索引的列，不允许为null，可能会得到不符合预期的结果
当需要进行表连接的时候，最好不要超过三张表，因为需要join的字段，数据类型必须一致
能使用 limit 的时候，尽量使用 limit
单表索引建议控制在5个以内
组合索引中单索引字段在5个以内
索引的正确概念：
- 索引不是越多越好；索引也是要维护的，过多时会降低性能
- 在不了解系统的情况下，不要过早优化
  
  2、存储引擎
  
  常用的：MyIsam、InnoDB
  
  2.1 InnoDB索引原理
  
  互联网大多数应用是读多写少的，读写比例可达10:1；并且数据库在做查询时IO消耗较大，理论上，B+树的查找时间复杂度为log1.44(n)，是大于logn的。从下图可以发现，MySQL是由一个个磁盘块组成的树形结构。每个磁盘块由数据项和指针组成。且所有的数据都是存放在叶子磁盘节点，非叶子磁盘节点不存放数据。
  
  2.1.1查找过程
  
  以磁盘块1为例，指针 P1 表示小于17的磁盘块，P2 表示在 17~35 之间的磁盘块，P3 则表示大于35的磁盘块。
  
  比如要查找数据项99，首先将磁盘块1 load 到内存中，发生 1 次 IO。接着通过二分查找发现 99 大于 35，所以找到了 P3 指针。通过P3 指针发生第二次 IO 将磁盘块4加载到内存。再通过二分查找发现大于87，通过 P3 指针发生了第三次 IO 将磁盘块11 加载到内存。最后再通过一次二分查找找到了数据项99。
  
  由此可见，如果一个几百万的数据查询只需要进行三次 IO 即可找到数据，那么整个效率将是非常高的。
  观察树的结构，发现查询需要经历几次 IO 是由树的高度来决定的，而树的高度又由磁盘块、数据项（主键）的大小决定的。
  磁盘块越大，数据项越小那么树的高度就越低。这也就是为什么索引字段要尽可能小的原因。
  
  2.2 InnoDB的内存架构主要分为三大块，缓冲池（Buffer Pool）、重做缓冲池（Redo Log Buffer）和额外内存池
  
  2.2.1 缓冲池
  
  InnoDB为了做数据的持久化，会将数据存储到磁盘上。但是面对大量的请求时，CPU的处理速度和磁盘的IO速度之间差距太大，为了提高整体的效率， InnoDB引入了缓冲池。
  
  当有请求来查询数据时，如果缓存池中没有，就会去磁盘中查找，将匹配到的数据放入缓存池中。同样的，如果有请求来修改数据，MySQL并不会直接去修改磁盘，而是会修改已经在缓冲池的页中的数据，然后再将数据刷回磁盘，这就是缓冲池的作用，加速读，加速写，减少与磁盘的IO交互。
  
  缓冲池说白了就是把磁盘中的数据丢到内存，那既然是内存就会存在没有内存空间可以分配的情况。所以缓冲池采用了LRU算法，在缓冲池中没有空闲的页时，来进行页的淘汰。但是采用这种算法会带来一个问题叫做缓冲池污染。
  
  当你在进行批量扫描甚至全表扫描时，可能会将缓冲池中的热点页全部替换出去。这样以来可能会导致MySQL的性能断崖式下降。所以InnoDB对LRU做了一些优化，规避了这个问题。
  
  MySQL采用日志先行，在真正写数据之前，会首先记录一个日志，叫Redo Log，会定期的使用CheckPoint技术将新的Redo Log刷入磁盘.
  
  除了数据之外，里面还存储了索引页、Undo页、插入缓冲、自适应哈希索引、InnoDB锁信息和数据字典。下面选几个比较重要的来简单聊一聊。
  
  ①插入缓冲
  
  插入缓冲针对的操作是更新或者插入，我们考虑最坏的情况，那就是需要更新的数据都不在缓冲池中。那么此时会有下面两种方案。
  1. 来一条数据就直接写入磁盘
  2. 等数据达到某个阈值（例如50条）才批量的写入磁盘
  很明显，第二种方案要好一点，减少了与磁盘IO的交互。
  
  2.2.2自适应哈希索引
  
  自适应索引就跟JVM在运行过程中，会动态的把某些热点代码编译成Machine Code一样，InnoDB会监控对所有索引的查询，对热点访问的页建立哈希索引，以此来提升访问速度。
  
  2.2.3重做日志缓冲
  
  上面聊过，InnoDB中缓冲池中的页数据更新会先于磁盘数据更新的，InnoDB也会采用日志先行（Write Ahead Log）策略来刷新数据，什么意思呢？当事务开始时，会先记录Redo Log到Redo Log Buffer中，然后再更新缓冲池页数据。
  
  Redo Log Buffer中的数据会按照一定的频率写到重做日志中去。被更改过的页就会被标记成脏页，InnoDB会根据CheckPoint机制来将脏页刷到磁盘。
  
  补：日志
  
  MySQL层面
  
  InnoDB层面

1.MySQL日志

  MySQL的日志可以分为错误日志、二进制文件、查询日志和满查询日志。

错误日志 很好理解，就是服务运行过程中发生的严重错误日志。当我们的数据库无法启动时，就可以来这里看看具体不能启动的原因是什么
二进制文件 它有另外一个名字你应该熟悉，叫Binlog，其记录了对数据库所有的更改。
查询日志 记录了来自客户端的所有语句
慢查询日志 这里记录了所有响应时间超过阈值的SQL语句，这个阈值我们可以自己设置，参数为long_query_time，其默认值为10s，且默认是关闭的状态，需要手动的打开。

2.InnoDB日志

InnoDB日志就只有两种，Redo Log和Undo Log，

Redo Log 重做日志，用于记录事务操作的变化，且记录的是修改之后的值。不管事务是否提交都会记录下来。例如在更新数据时，会先将更新的记录写到Redo Log中，再更新缓存中页中的数据。然后按照设置的更新策略，将内存中的数据刷回磁盘。
Undo Log 记录的是记录的事务开始之前的一个版本，可用于事务失败之后发生的回滚。

Redo Log记录的是具体某个数据页上的修改，只能在当前Server使用，而Binlog可以理解为可以给其他类型的存储引擎使用。这也是Binlog的一个重要作用，那就是主从复制，另外一个作用是数据恢复。

上面提到过，Binlog中记录了所有对数据库的修改，其记录日志有三种格式。分别是Statement、Row和MixedLevel。
- Statement 记录所有会修改数据的SQL，其只会记录SQL，并不需要记录下这个SQL影响的所有行，减少了日志量，提高了性能。但是由于只是记录执行语句，不能保证在Slave节点上能够正确执行，所以还需要额外的记录一些上下文信息

Row 只保存被修改的记录，与Statement只记录执行SQL来比较，Row会产生大量的日志。但是Row不用记录上下文信息了，只需要关注被改成啥样就行。

MixedLevel 就是Statement和Row混合使用。

具体使用哪种日志，需要根据实际情况来决定。例如一条UPDATE语句更新了很多的数据，采用Statement会更加节省空间，但是相对的，Row会更加的可靠。

------------------------------MyISAM 和 InnoBD区别：----------------------

	MyISAM	InnoDB
主键	允许没有任何索引和主键的表存在，myisam的索引都是保存行的地址。	如果没有设定主键或者非空唯一索引，就会自动生成一个6字节的主键(用户不可见)innodb的数据是主索引的一部分，其他索引保存的是主索引的值。
事务处理上方面:	MyISAM类型的表强调的是性能，其执行数度比InnoDB类型更快，但是不提供事务支持、不支持外键	InnoDB提供事务支持事务，外部键（foreign key）等高级数据库功能
DML操作	如果执行大量的SELECT，MyISAM是更好的选择	1.如果你的数据执行大量的INSERT或UPDATE，出于性能方面的考虑，应该使用InnoDB表 2.DELETE FROM table时，InnoDB不会重新建立表，而是一行一行的删除。
自动增长	myisam引擎的自动增长列必须是索引，如果是组合索引，自动增长可以不是第一列，他可以根据前面几列进行排序后递增。	innodb引擎的自动增长必须是索引，如果是组合索引也必须是组合索引的第一列。
count()函数	myisam保存有表的总行数，如果select count(*) from table;会直接取出出该值	innodb没有保存表的总行数，如果使用select count(*) from table；就会遍历整个表，消耗相当大，但是在加了wehre 条件后，myisam和innodb处理的方式都一样。
锁	表锁	提供行锁，另外，InnoDB表的行锁也不是绝对的，如果在执行一个SQL语句时MySQL不能确定要扫描的范围，InnoDB表同样会锁全表，例如update table set num=1 where name like “%aaa%”