欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

week09_day03_索引02

程序员文章站 2022-03-09 09:17:54
...
总结
事务
	a.概念
	b.基本操作
		开启事务:begin/start transaction, set autocommit=0
		提交事务:commit
		设置回滚点:savepoint sp 
		删除回滚点:release savepoint sp 
		回滚:rollback, rollback to sp
		设置隔离级别:set transaction 
	c.特性
		原子性
		一致性
		隔离性
		持久性
	d.并发执行事务可能会出现的问题
		脏写
		脏读
		不可重复读
		幻读
	e.隔离级别
						脏写	脏读	不可重复读	幻读 
	read uncommitted	×		√			√		√
	read committed		×		×			√		√
	repeatable read		×		×			×		√
	serialize			×		×			×		×


索引
	a. MySQL逻辑架构
		连接器
		查询缓存
		解析器
		优化器
		执行器
	b. 存储引擎
		MyISAM
		InnoDB
		Memory
	c. 磁盘IO原理
	
	d. InnoDB数据页格式
	
	e. 有哪些数据结构可以快速地查找数据
		有序数组
		哈希表
		平衡二叉树
		

索引是什么?

简单来说,索引的目的就是为了提高数据的查询效率,就像书的目录一样。
一本800页的书,如果想在书中查找某个知识点。在不借助目录的情况下,估计得找好一会儿。同样,对于数据库的表而言,索引就是它的 ”目录”。

索引:在 MySQL 中也叫做键 (key),是存储引擎用于快速找到记录的一种数据结构。

·················································································································································································································

哪些数据结构可以作为索引?

  • 有序数组
  • 哈希表 (hash索引)
  • 平衡二叉树
  • B树
  • B+树

能够快速查找的数据结构都可以作为索引。
能够讲讲作为索引时,各个数据结构的优缺点吗?

有序数组:等值查找,区间查找都比较块。但是增删需要移动大量的元素,会很慢。

哈希表:增加、删除,等值查询都很快。但是区间查找,排序等操作会很慢。(因为哈希表中的元素都是无序的)

平衡二叉树索引
week09_day03_索引02
不管是,增加,删除,还是等值查找,时间复杂度都是O(logn),n 是数据页的数目。
并且支持范围查找(BST有序)。

但是当数据量比较大,页的数目很多时,二叉树的高度会比较高。IO 的次数会比较多。
查找效率低。
比如说,有1024个页,那么树的高度为10,查找一个结点需要花0.1s,查找到目标结点就需要花1s,时间略长。

    1. 移动磁头到指定的柱面号,这个过程被称为定位或查找。
         由于是机械移动, 这部分耗时最高, 最大可达 0.1s.

那我们就想,怎么把树的高度降低呢? B树

·················································································································································································································

B树索引

B 树,它是一颗多路平衡查找树。我们描述一颗 B 树时需要指定它的阶数,阶数表示了一个结点最多有多少个孩子,一般用字母m表示。一颗m阶的B树定义如下:

1)除根结点外,每个结点的度[ceil(m/2), m]。

2)根结点的度[2, m]

3)每个结点中的关键字都按照从小到大的顺序排列,每个关键字的左子树中的所有关键字都小于它,而右子树中的所有关键字都大于它。

4)所有叶子结点都位于同一层,或者说根结点到每个叶子结点的路径长度都相同。

week09_day03_索引02
这是一棵4阶B树,从图中我们可以看出: 索引和数据是一起存放的

之前讲存储引擎的时候有这么一句话:

在InnoDB存储引擎中,有很多种页类型。其中最重要的是数据页,也叫 B-tree Node。(说明数据页是作为B+树的结点存在的),里面存储了索引和数据的信息。

也就是说一个结点存放了一页的数据。

假设一行记录是16B,那么一页大概可以存1000行记录,即B树的阶是1000。二层的B树大概可以存1000 * 1000行记录,三层可以存 1000 * 1000 * 1000 行记录。大大减少了树的高度,也就是减少了一次查找IO的次数。

那么,它有什么缺点吗?

  1. 一行记录的数据很多时,比如1K。
    第一层:16
    第二层:1616
    第三层:16
    16*16
    当一棵树的数据量很大时,树的高度也会很大,查找的效率依然会比较低。

  2. 范围查找时,性能会下降。
    如:上面那棵树,找[25,50]的结点,找25,3次IO,找50,2次IO(找25时已经保存了根节点39了,不用再进行1次IO了)。至少5次IO。
    我们发现,范围查找时会

·················································································································································································································

B+树索引

B+ 树是在B树上做了些改进。一棵 m 阶的 B+ 树定义如下:

1)B+树包含2种类型的结点:内部结点 (也称索引结点) 和叶子结点。根结点即可以是内部结点,也可以是叶子结点。根结点的关键字个数可以只有1个。

2)B+树与B树最大的不同是内部结点不保存数据,只保存关键字,所有数据 (记录) 都保存在叶子结点中。

3) m阶B+树表示了内部结点最多有m个关键字。至少有 ceiling(m/2)个关键字。

4)内部结点中的key都按照从小到大的顺序排列,叶子结点中的记录也按照key的大小排列。

5)每个叶子结点都存有相邻叶子结点的指针,叶子结点依关键字大小依次链接。

week09_day03_索引02
这是一棵 3阶的 B+ 树。由于内部节点只存储索引,因而每个节点可以有很多很多关键字。这样不管一行记录的数据大小,都可以保证树的高度很低。

假设一页可以存储20条记录, 1000个索引。那么:
如果只有1层:20
如果有2层:1000 * 20
如果有3层:1000 * 1000 * 20

之前B树存的是记录,现在B+树存的是索引,索引所占的空间是小于记录的,因此每一页都能存储更多的索引,这样就解决了第一个问题:树的增长过快。

而且由于叶子节点是由链表按大小依次连接(有序)的 (在InnoDB 中是双链表)。范围查找的时候,也可以避免过多的IO次数。
例如查找[25,50]之间的数据,找到25后一直向后遍历直至50即可。
再比如进行全表扫描,找到data结点,然后一直向后遍历即可,无需遍历中间结点,直接遍历叶子结点。

前面讲的数据页就是B+树的叶子结点。
页与页之间通过链表连接,并且页内有序。

·················································································································································································································

索引的好处和坏处

好处
提高数据检索的效率,降低数据库的IO成本。
a. 查找
b. 排序
c. 分组
d. 表的连接
如:Select * from t1 inner join t2 on t1.id = t2.id;(inner可以省略,表示内连接)
首先遍历t1表的第一条记录,t1.id就确定了,接下来去t2表中找有无和t1.id相同的id字段,有的话就拼接起来,放在结果集中。
对于t2来说,我们要找某条记录的id等于t1.id的记录,就会用到查询。
所以,索引也会加快表的连接。

坏处
a. 占用额外的空间。有时候索引占用的空间甚至比数据占用的空间还多。
b. 虽然索引大大提高了查询的速度,但同时也降低了更新表的速度。因为数据库不仅仅要更新数据,还要更新对应的索引信息。

索引不是越多越好!索引太多,应用程序的性能可能会受到影响; 索引太少,查询速度会变慢。我们应该建立合适的索引,找到一个平衡点!

·················································································································································································································

InnoDB索引介绍

InnoDB 支持以下三种索引:

  • B+ 树索引
  • 全文索引 .
    全文索引是搜索关键字的,类似于搜索引擎。
  • 哈希索引
    哈希索引是自适应的,我们不能自己创建。
    Innodb会为热点数据创建哈希索引。热点数据即我们经常查询的数据。
    哈希索引直接根据键查找值,只遍历一个结点即可。

·················································································································································································································

InnoDB 中的 B+ 树索引又可以分为聚集索引 (clustered index) 和 辅助索引 (secondary index)。它们之间的不同在于,聚集索引的叶子节点存储的是一整行记录的信息,而辅助索引的叶子节点只存放部分信息 (关键字和主键)。

聚集索引

聚集索引就是按照每张表的主键构建一棵 B+ 树,同时叶子节点中存放的是整张表的行记录数据。

聚集索引的叶子节点其实就是我们前面讲过的数据页。

在InnoDB中, 记录只能存放在聚集索引中,所以每张表有且只有一个聚集索引。在大多数情况下,查询优化器倾向于采用聚集索引。
week09_day03_索引02
Q:如果一张表中没有主键,该怎么办呢?
a.找第一个定义的唯一键去构建聚集索引。
b.如果没有定义唯一键,又该怎么办呢?Innodb会提供隐藏的主键,根据隐藏的主键去构建聚集索引。
所以,建议创建表的时候一定要创建主键。

辅助索引

对于辅助索引,叶子节点不包含行记录的全部数据,叶子节点除了包含键以外,
还包含聚集索引的键,也就是主键的信息。

辅助索引的存在并不影响数据在聚集索引中的组织,因此每张表可以有多个辅助索引。

week09_day03_索引02
Q:有一张公民表,有身份证号码、姓名、年龄、性别…等信息,
我们知道公民的身份证号码是唯一并且非空的,那么用身份证号码当主键好吗?

不好,身份证号是varchar类型(有的身份证号含有x字母),会更耗费磁盘空间,且不方便比较。
当根据姓名进行查找或者根据年龄进行查找,就得建立一个辅助索引。
每个结点的大小是固定的,(页默认大小为16KB),主键所占的空间比较大的话,一个结点存放的主键个数就少,就需要多个结点存储,结点一多,树的高度就可能变高。
主键所占的空间比较大的话,每次创建一个辅助索引就会耗费比较大的空间(辅助索引的叶子结点存储的是主键的信息)。
因此,创建公民表时会额外给一个整数型id当做主键。

所以这也就是为什么主键通常是int型的,int占4字节。varchar和string占的字节数更多。

·················································································································································································································

语法

  1. 创建:
    1) 创建表的时候指定。会自动给 primary key 和 unique 创建索引。
    2) CREATE [UNIQUE] INDEX 索引名 ON 表名(字段列表);
    3) ALTER 表名 ADD [UNIQUE] INDEX 索引名 (字段列表);
  2. 删除:
    DROP INDEX 索引名 ON 表名;
    删除主键索引只能通过删除表的方式删除
  3. 查看:
    SHOW INDEX FROM 表名;

·················································································································································································································

回表

假设t_citizen只有两个索引:id的主键(聚集)索引和id_card的辅助索引
思考下面SQL语句的执行过程:

  1. select id from t_citizen where id =1; # 会走聚集索引,因为 where id =1;
  2. select id_card from t_citizen where id_card = ‘’; # 会走id_card的辅助索引,因为where id_card = ‘’
  3. select name from t_citizen where id = 1; # 会走聚集索引
  4. select name from t_citizen where id_card = ‘’; # 先走辅助索引id_card,找到主键id,找到后走聚集索引,查找name
  5. select * from t_citizen where id = 1; # 聚集索引
  6. select * from t_citizen where id_card = ‘’; # 先走辅助索引id_card,找到主键id,找到后走聚集索引,查找*

当通过辅助索引来寻找数据的时候,InnoDB会遍历辅助索引,并通过辅助索引的叶子节点,获取主键。然后再通过聚集索引来找到一个完整的行记录。这个过程我们称之为回表。

如果一个辅助索引的高度为3,聚集索引的高度为3。那么我们需要6次IO操作,才可以访问最终的数据。

应该尽量避免回表!

很多情况下,我们需要通过身份证号码(不是主键),查询这个人的名字和年龄,怎么做才能避免回表呢?

这个问题明天将。

·················································································································································································································

Explain 介绍

查询优化器:通过计算分析系统收集的统计信息,提供它认为最优的执行计划(execution plan)。

explain:查看这个执行计划的信息。

语法:explain + select 语句

例子:explain select * from t;

我们发现explain的结果有以下列的信息:
id, select_type, table, partitions, type, possible_keys, key, ken_len, ref, rows, filtered, Extra

id: 每个 select 子句的标识。

select_type: select 语句的类型。simple, primary, union, subquery, derived。

table:显示这一行的数据是关于哪张表的。

partitions: 匹配的分表。

type: 连接类型,又叫 “访问类型”。
常用类型有:ALL, index, range, ref, eq_ref, const, system, null
(从左到右,性能越来越好)

possible_keys:可以选择的索引。

key: 实际选择的索引。

key_len: 使用索引的长度 (以字节为单位)。

ref: 与索引比较的字段

rows: 大概要检索的行数(不准确的数据)

Extra: 额外信息。
using filesort: MySQL中无法利用索引完成的排序操作称为 ”文件排序”,常见于排序和分组查询。
using temporary: 表示MySQL需要使用临时表来存储结果集,常见于排序和分组查询。

using filesort 和 using temporary, 这两项比较耗时, 需要特别小心。最好避免这两项的出现。

·················································································································································································································