乐趣区

关于面试:面试官灵魂拷问什么是MySQL索引为什么需要索引

jiezi

为什么须要学 MySQL？

咱们每天都在拜访各种⽹站、APP，如微信、QQ、抖⾳、今⽇头条、腾讯新闻等，这些 货色上⾯都存在⼤量的信息，这些信息都须要有地⽅存储，存储在哪呢？数据库。

所以如果咱们须要开发⼀个⽹站、app，数据库咱们必须把握的技术，常⽤的数据库有 mysql、oracle、sqlserver、db2 等。

上⾯介绍的⼏个数据库，oracle 性能排名第⼀，服务也是相当到位的，然而免费也是⾮常 ⾼的，⾦融公司对数据库稳定性要求⽐较⾼，⼀般会抉择 oracle。

mysql 是收费的，其余⼏个⽬前临时免费的，mysql 在互联⽹公司使⽤率也是排名第⼀，材料也⾮常欠缺，社区也⾮常沉闷，所以咱们次要学习 mysql。

篇幅所限，本文只详写了 MySQL 索引，须要的同学可自行支付完整版 MySQL 学习笔记

一、什么是索引？

索引就好比字典的目录一样 咱们通常都会先去目录查找要害偏旁或者字母再去查找 要比间接翻查字典查问要快很多

二、为什么要有索引？

然而咱们在应用 mysql 数据库的时候也像字典一样有索引的状况上来查问，必定速度要快很多

2.1 问题：

1.mysql 数据存储在什么中央?

磁盘

2. 查问数据慢，个别卡在哪？

IO

3. 去磁盘读取数据，是用多少读取多少吗？

磁盘预读

局部性原理：数据和程序都有汇集成群的偏向，同时之前被拜访过的数据很可能再次被查问，空间局部性，工夫局部性

磁盘预读：内存和磁盘产生数据交互的时候，个别状况下有一个最小的逻辑单元，页。页个别由操作系统感觉大小，4k 或 8k，而咱们在进行数据交互的时候，能够取页的整数倍来读取。

关注公众号： 北游学 Java 即可获取一份 578 页 PDF 文档的 MySQL 学习笔记

innodb 存储引擎每次读取数据，读取 16k

4. 索引存储在哪？

磁盘，查问数据的时候会优先将索引加载到内存中

5. 索引在存储的时候，须要什么信息？须要存储存储什么字段值？

key: 理论数据行中存储的值

文件地址

offset：偏移量

6. 这种格局的数据要应用什么样的数据结构来进行存储？

key-values

哈希表，树 (二叉树、红黑树、AVL 树、B 树、B+ 树)

7.mysql 索引零碎中不是依照刚刚说的格局存储的，为什么？

OLAP: 联机剖析解决 —- 对海量历史数据进行剖析，产生决策性的策略 —- 数据仓库—Hive

OLTP: 联机事务处理 —- 要求很短时效内返回对应的后果 —- 数据库—关系型数据库 (mysql、oracle)

三、mysql 的索引数据结构

3.1 哈希表:

HashMap 数组加链表的构造，不适宜作为索引的起因：

1. 哈希抵触会造成数据散列不平均，会产生大量的线性查问，比拟浪费时间

2. 不反对范畴查问，当进行范畴查问的时候，必须挨个遍历

3. 对于内存空间的要求比拟高

长处： 如果是等值查问，十分快

在 mysql 中有没有 hash 索引?

1.memory 存储引擎应用的是 hash 索引

2.innodb 反对自适应 hash

create table test(id int primary key,name varchar(30))
engine='innodb/memory/myisam'
-- 5.1 之后默认 innodb

3.2 树：

树这种数据结构有很多，咱们常见的有： 二叉树、BST、AVL、红黑树、B 树、B+ 树

①二叉树：无序插入

这就是咱们的树的结构图，然而二叉树的数据插入是无序的，也就是说当须要查找的时候，还是得一个一个挨着去遍历查找

②BST(二叉搜寻树)： 插入的数据有序，左子树必须小于根节点，右子树必须大于根节点 ——– 应用二分查找来提高效率

这样的话如果要查问数据，能够通过二分查找，疾速放大范畴，缩小了工夫复杂度 ** 然而如果插入的程序是升序或者降序的话，树的形态会变成如下：

此时二叉搜寻树就会进化成链表，工夫复杂度又会变成 O(n)

③AVL：均衡二叉树 为了解决上述问题，通过左旋转或右旋转让树均衡 最短子树跟最长子树高度只差不能超过 1

由图咱们能够看到，当程序插入的时候，会主动的进行旋转，以达到均衡 然而会通过插入性能的损失来补救查问性能的晋升 当咱们插入的数据很多时候，而查问很少的时候，因为插入数据会旋转同样会耗费很多工夫

④红黑树 (解决了读写申请一样多) 同样是通过左右旋让树平衡起来，还要变色的行为 最长子树只有不超过最短子树的两倍即可

查问性能和插入性能近似获得均衡 然而随着数据的插入、发现树的深度会变深，树的深度会越来越深，意味着 IO 次数越多，影响数据读取的效率

⑤ B 树 为了解决上述数据插入过多，树深度变深的问题，咱们采纳 B 树 把原来的有序二叉树变成有序多叉树

举例： 如果要查问 select * from table where id=14？

  1. 第一步，将磁盘一加载到内存中，发现 14<16, 寻找地址磁盘 2
  2. 第二步，将磁盘二加载到内存中，发现 14>11, 寻找地址磁盘 7
  3. 第三步，将磁盘七加载到内存中，发现 14=14，读取 data，取出 data，完结 思考：B 树就是完满的嘛？
    问题 1： 
    B 树不反对范畴查问的疾速查找，如果咱们查问一个范畴的数据，查找到范畴一个边界时，须要回到根节点从新遍历查找，须要从根节点进行屡次遍历，即使找到范畴的另一个边界，查问效率会升高。
    问题 2： 
    如果 data 存储的是行记录，行的大小随着列数的增多，所占空间会变大。这时，一个页中可存储的数据量就会变少，树相应就会变高，磁盘 IO 次数就会变大。思考 2：三层 B 树可能存储多少条记录？
    答: 假如一个 data 为 1k，innodb 存储引擎一次读取数据为 16k，三层即 161616=4096；然而往往在开发中，一个表的数据要远远大于 4096，难道要持续加层，这样岂不就加大了 IO

四、为什么应用 B + 树？

理论存储表数据的时候，怎么存储呢？ key 残缺的数据行 革新 B + 树

B+ 树对 B 树进行了改良，把数据全放在了叶子节点中，叶子节点之间应用双向指针连贯，最底层的叶子节点造成了一个双向有序链表。
例如： 
查问范畴 select * from table where id between 11 and 35？

  1. 第一步，将磁盘一加载到内存中，发现 11<28, 寻找地址磁盘 2
  2. 第二步，将磁盘二加载到内存中，发现 10>11>17, 寻找地址磁盘 5
  3. 第三步，将磁盘五加载到内存中，发现 11=11，读取 data
  4. 第四步，持续向右查问，读取磁盘 5，发现 35=35，读取 11-35 之间数据，完结 由此可见，这样的范畴查问比 B 树速度进步了不少

比照 B 树和 B + 树？

  • 叶子节点中才放数据
  • 非叶子节点中不存储数据
  • B+ 树每个节点蕴含更多个节点，这样做的益处，能够升高树的高度，同时将数据范畴变成多个区间，区间越多查问越快

问题： 创立索引时用 int 还是 varchar？

答：视状况而定，然而记住肯定让 key 越小越好

五、索引的创立

在创立索引之前，我先说一下存储引擎 存储引擎： 示意不同的数据在磁盘的不同表现形式 大家去察看 mysql 的磁盘文件会发现 innodb： innodb 的数据和索引都存储在一个文件下.idb myisam： myisam 的索引存储在.MYI 文件中，数据存储在.MYD 中

5.1 聚簇索引和非聚簇索引

概念：判断是否是聚簇索引就看数据和索引是否在一个文件中 innodb：

  1. 只能有一个聚簇索引，然而有很多非聚簇索引
  2. 向 innodb 插入数据的时候，必须要蕴含一个索引的 key 值
  3. 这个索引的 key 值，能够是主键，如果没有主键，那么就是惟一键，如果没有惟一键，那么就是一个自生成的 6 字节的 rowid

myisam： 非聚簇索引

MySQL—innodb—-B+ 树 索引和数据存储在一起，找到索引即可读取对应的数据

MySQL—myisam—-B+ 树 索引和存储数据的地址在一起，找到索引失去地址值，再通过地址找到对应的数据

5.2 回表

接下来，我会创立一张案例表给大家展现 

CREATE TABLE user_test(
id INT PRIMARY KEY AUTO_INCREMENT,-- id 为主键
uname VARCHAR(20) ,
age INT,
gender VARCHAR(10),
 KEY `idx_uname` (`uname`) -- 索引抉择为名字
)ENGINE = INNODB;

INSERT INTO user_test VALUES(1,'张三',18,'男');
INSERT INTO user_test VALUES(NULL,'马冬梅',19,'女');
INSERT INTO user_test VALUES(NULL,'赵四',18,'男');
INSERT INTO user_test VALUES(NULL,'王老七',22,'男');
INSERT INTO user_test VALUES(NULL,'刘燕',16,'女');
INSERT INTO user_test VALUES(NULL,'万宝',26,'男');

select * from user_test where uname = '张三';
-- 当咱们表中有主键索引的时候，咱们再去设置一个 uname 为索引，那么此时这条 sql 语句的查问过程应该如下：

首先先依据 uname 查问到 id，再依据 id 查问到行的信息 这样的操作走了两棵 B + 树，就是回表 当依据一般索引查问到聚簇索引的 key 值之后，再依据 key 值在聚簇索引中获取数据 咱们能够发现这样的操作是很浪费时间的，因而咱们日常操作的时候，尽量减少回表的次数

5.3 笼罩索引 

select id,uname from table where uname = '张三';
-- 依据 uname 能够间接查问到 id，uname 两个列的值，间接返回即可
-- 不须要从聚簇索引查问任何数据，此时叫做索引笼罩

5.4 最左匹配

在说最左匹配之前，咱们先聊一下几个名词 主键 (个别为一个列)——–> 联结主键 (多个列) 索引 ——–> 联结索引 (可能蕴含多个索引列)

-- 假如有一张表，有 id，name，age，gender 四个字段，id 是主键，name，age 是组合索引列
-- 组合索引应用的时候必须先匹配 name，而后匹配 age

select * from table where name = ? and age = ? ;-- 失效
select * from table where name = ?;-- 失效
select * from table where age = ? ;-- 不失效
select * from table where age = ? and name = ? ;-- 失效

-- 在 mysql 外部有优化器会调整对应的程序

5.5 索引下推

mysql5.7 之后，默认反对的一个特点 举一个例子：

select * from table where name = ? and age = ? ;
-- mysql 里的三层架构:
-- 客户端:JDBC
-- 服务端:server
-- 存储引擎: 数据存储
在没有索引下推之前，依据 name 从存储引擎中获取合乎规定的数据，在 server 层对 age 进行过滤
有索引下推之后，依据 name、age 两个条件从存储引擎中获取对应的数据

剖析：有索引下推的益处，如果咱们有 50 条数据，咱们通过过滤会失去 10 条数据，如果没有索引下推，会先获取 50 条再去排除失去 10 条，而有了下推之后，咱们会间接在存储引擎就过滤成了 10 条

退出移动版