IT小白

这个屌丝很懒，什么也没留下！

热门标签

MySQL索引学习篇_索引的分类、测试100万数据有无索引查询速度对比、索引深入（聚集索引、索引的数据结构、B树和B+树的区别 B+树的优势、MyISAM 和 InnoDB 索引组织的区别）_一百万数据查询二叉树和b树,哪个快

作者：IT小白 | 2024-04-17 09:23:37

踩

一百万数据查询二叉树和b树,哪个快

一、索引的分类

索引的概念

官方对索引的定义为：索引（Index）是帮助数据库高效获取数据的数据结构
区别于数据库引擎（介绍参考：https://www.cnblogs.com/0201zcr/p/5296843.html）概念，常见的数据库引擎MyIASM和Innodb都使用了树这种数据结构做为索引。

索引的分类

主键索引(PRIMARY)：唯一的标识，主键不可重复，只能有一个列作为主键
唯一索引(UNION)：避免重复的列出现，多个列都可以设置
常规索引(KEY)
全文索引(FULLTEXT)

举栗

/*
SQLyog Ultimate v12.09 (64 bit)
MySQL - 5.7.11-log : Database - educ
*********************************************************************
*/


/*!40101 SET NAMES utf8 */;

/*!40101 SET SQL_MODE=''*/;

/*!40014 SET @OLD_UNIQUE_CHECKS=@@UNIQUE_CHECKS, UNIQUE_CHECKS=0 */;
/*!40014 SET @OLD_FOREIGN_KEY_CHECKS=@@FOREIGN_KEY_CHECKS, FOREIGN_KEY_CHECKS=0 */;
/*!40101 SET @OLD_SQL_MODE=@@SQL_MODE, SQL_MODE='NO_AUTO_VALUE_ON_ZERO' */;
/*!40111 SET @OLD_SQL_NOTES=@@SQL_NOTES, SQL_NOTES=0 */;
CREATE DATABASE /*!32312 IF NOT EXISTS*/`educ` /*!40100 DEFAULT CHARACTER SET utf8 */;

USE `educ`;

/*Table structure for table `course` */

DROP TABLE IF EXISTS `course`;

CREATE TABLE `course` (
  `Cno` BIGINT(20) NOT NULL,
  `Cname` VARCHAR(20) DEFAULT NULL,
  `Cpno` VARCHAR(10) DEFAULT NULL COMMENT '先行课',
  `Ccredit` VARCHAR(10) DEFAULT NULL,
  PRIMARY KEY (`Cno`),    =========================> 主键索引
  UNIQUE KEY `Cname` (`Cname`) ====================> 唯一索引
) ENGINE=INNODB DEFAULT CHARSET=utf8;==============> 数据库引擎

/*Data for the table `course` */

INSERT  INTO `course`(`Cno`,`Cname`,`Cpno`,`Ccredit`) VALUES (1,'数据库','5','4'),(2,'数学',NULL,'2'),(3,'信息系统','1','4'),(4,'操作系统','6','3'),(5,'数据结构','7','4'),(6,'数据处理',NULL,'2'),(7,'PASCAL语言','6','4');

/*!40101 SET SQL_MODE=@OLD_SQL_MODE */;
/*!40014 SET FOREIGN_KEY_CHECKS=@OLD_FOREIGN_KEY_CHECKS */;
/*!40014 SET UNIQUE_CHECKS=@OLD_UNIQUE_CHECKS */;
/*!40111 SET SQL_NOTES=@OLD_SQL_NOTES */;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

增加索引举栗

增加的sql有三种形式：
- 建立表的时候
- alter table add index xxx
- create index on xxx table(xxxCol)
设置全文索引：ALTER TABLE educ.student ADD FULLTEXT INDEXSage(Sage);
查看表的索引：SHOW INDEX FROM student

二、测试索引（场景插入100万数据）

1.基本步骤

写函数插入100万数据

DELIMITER $$

CREATE FUNCTION mock_data()
RETURNS INT
BEGIN
	DECLARE num INT DEFAULT 1000000;
	DECLARE i INT DEFAULT 1;
	WHILE i<=num DO
		INSERT INTO USER(`name`,`email`,`phone`,`password`,`age`)
		VALUES(
		CONCAT('用户',i),
		'2589165806@qq.com',
		CONCAT('17',FLOOR(RAND()* 999999999)),
		UUID(),
		FLOOR(RAND() * 100));
		
		SET i = i + 1;
	END WHILE;
	RETURN i;
END


SELECT mock_data();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

耗时41s
EXPLAIN测试select查询：EXPLAIN SELECT * FROM USER WHERE NAME = '用户99999';
根据name字段创建索引：CREATE INDEX id_user_name ON USER(`name`)
再次测试查询

2.sql脚本

DELIMITER $$

CREATE FUNCTION mock_data()
RETURNS INT
BEGIN
	DECLARE num INT DEFAULT 1000000;
	DECLARE i INT DEFAULT 1;
	WHILE i<=num DO
		INSERT INTO USER(`name`,`email`,`phone`,`password`,`age`)
		VALUES(
		CONCAT('用户',i),
		'2589165806@qq.com',
		CONCAT('17',FLOOR(RAND()* 999999999)),
		UUID(),
		FLOOR(RAND() * 100));
		
		SET i = i + 1;
	END WHILE;
	RETURN i;
END


SELECT mock_data();

SELECT * FROM USER;

SELECT * FROM USER WHERE NAME = '用户99999'; # 总耗时      : 0.692 sec

EXPLAIN SELECT * FROM USER WHERE NAME = '用户99999';

# 创建索引
CREATE INDEX id_user_name ON USER(`name`)

# 创建索引之后的查询

SELECT * FROM USER WHERE NAME = '用户99999'; # 总耗时      :  0.009 sec

EXPLAIN SELECT * FROM USER WHERE NAME = '用户99999'; # 1rows




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

三、索引原则

注意

索引不是越多越好
不要对经常变动的数据加索引
少量数据不需要加索引
索引一般加在常用来查询的字段上

四、索引深入

1.聚集（主键）索引

InnoDB存储引擎是 B+ 树索引组织的，所以数据即索引，索引即数据。B+ 树的叶子节点存储的都是数据段的数据。
InnoDB 引擎对数据的存储必须依赖于主键，主键对应的索引叫做聚集索引。如果不幸的是你建表没有建主键，InnoDB 会从表字段中寻找第一个非空的唯一索引作为聚集索引，如果还是不幸找不到，InnoDB 会生成一个不可见的名为 ROW_ID 的列，该列是一个 6 字节的自增数字，用来创建聚集索引。
对于 ROW_ID 列的自增实现其实是来自于一个全局自增序列，这意味着所有使用到 ROW_ID 作为聚集索引的表都共享该序列，如果在高并发的情况就有保证不了唯一性的可能。

2.索引的数据结构

二叉树：对于二叉树而言，每个节点只能有两个子节点，如果是一颗单边二叉树，查询某个节点的次数与节点所处的高度相同，时间复杂度为O(n)；如果是一颗平衡二叉树，查找效率高出一半，时间复杂度为O(Log2n)。
B tree ：B树是二叉树的升级版，又叫平衡多路查找树。（外形可以看成分段数组上挂树，挂的树区间为该段区间）
Hash表：散列表的好处是散列查询单条数据比较快，但是坏处也比较多，比如 Hash 碰撞的解决，范围查找等等。
B+ tree ：B+ 树是应文件系统所需而产生的一种 B 树的变形树（文件的目录一级一级索引，只有最底层的叶子节点（文件）保存数据）非叶子节点只保存索引，不保存实际的数据）。
…

3.B树和B+树的区别

这里有一个很重要的一点就是 B+ 树的非叶子节点不保存数据，只有索引。

也就是所有的数据全放在最底层的叶子节点上，而且最底层的叶子节点是按照从小到大指针串起来的

一棵 m 阶的 B+ 树和 m 阶的 B 树的异同点在于：

节点的子树数和关键字数相同（B 树是关键字数比子树数少一）；
所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针（B树节点的关键字表示的是子树中的最大数，在子树中同样含有这个数据），
且叶子结点本身依关键字的大小自小而大的顺序链接。 (而 B 树的叶子节点并没有包括全部需要查找的信息)；
所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而 B 树的非终节点也包含需要查找的有效信息)。
叶子节点之间通过指针连接。

4. B+树的优势

对于 B 树和 B+ 树来说，两种数据结构都是为了减少磁盘 I/O 读写过于频繁而生，本身节点的个数是有限的，采用多叉结构就是为了让每一层放尽可能多的节点以此来降低整棵树的高度。但是为什么 InnoDB 索引结构最终选择了 B+ 树而不是B 树呢？

B+ 树的磁盘读写代价更低
B+ 树内部非叶子节点本身并不存储数据，所以非叶子节点的存储代价相比 B 树就小的多。存储容量减少同时也缩小了占用盘块的数量，那么数据的聚集程度直接也影响了查询磁盘的次数。
B+ 树查询效率更加稳定
树高确定的前提下所有的数据都在叶子节点，那么无论怎么查询所有关键字查询的路径长度是固定的。
B+ 树对范围查询的支持更好
B+ 树所有数据都在叶子节点，非叶子节点都是索引，那么做范围查询的时候只需要扫描一遍叶子节点即可；而 B 树因为非叶子节点也保存数据，范围查询的时候要找到具体数据还需要进行一次中序遍历。

5.MyISAM 和 InnoDB 索引组织的区别

在 MYSQL 中索引属于存储引级别的概念，存储引擎不同，索引的实现方式也不一样。

MyISAM 也是使用 B+ 树作为索引存储结构，他的叶子节点 data 域存放的是数据的物理地址，即索引结构和真正的数据结构其实是分开存储的。也就是data放的是指针。
MyISAM 索引和数据是分离的，但是在 InnoDB 中却大不相同，InnoDB 中采用主键索引的方式，所有的数据都保存在主键索索引中。即主键直接挂记录，基于主键来组织数据。

索引的类型

聚集（主键）索引
二级索引：除了主键索引之外的索引，二级索引B+树的叶子节点存储的不是数据，而是主键索引对应的主键值（也就是主键叶子节点的指针），查数据的时候，进行两次B+ 树查找
- 先查找二级索引 B+ 树，找到指向主键索引 B+ 树对应的叶子值
- 在查找主键索引 B+ 树，找到该叶子节点对应的行记录数据
覆盖索引：简单来说就是只查询索引就能获取到数据不必再回表查询，换句话说要查询的列已经被索引列覆盖。
联合索引：对多个字段建立一个索引，有一个 左前匹配原则 需要注意，也就是确保查询走的是联合索引而不是扫全表

6.索引的缺点

缺点

磁盘空间占用。这个对于当前磁盘比买菜还便宜的硬件大通货时代其实算不上问题，但是要注意的是如果当前 MySQL 服务所在的机器有很多的大表，并且还创建了每一种可能的组合的索引，那么索引文件提及的增长可能超乎你的想象。
维护索引对更新类操作所带来的耗时。当对索引涉及到的列做更新或者新增操作时都会去维护相关的索引，这里也是一个耗时的点，所以索引不在多，而在精。

参考：https://blog.codinglabs.org/articles/theory-of-mysql-index.html

本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/439432

MySQL索引学习篇_索引的分类、测试100万数据有无索引查询速度对比、索引深入（聚集索引 、索引的数据结构 、B树和B+树的区别 B+树的优势 、MyISAM 和 InnoDB 索引组织的区别 ）_一百万数据查询二叉树和b树,哪个快

目录