登不上建设企业网站,wordpress通过id获取文章,广州自助建站软件,.net做网站后台目录
1、索引简介
1.1 什么是索引
1.2 使用索引的原因
2、索引中数据结构的设计 —— B树
2.1 哈希
2.2 二叉搜索树
2.3 B树 2.4 最终选择之——B树
2.4.1 B树与B树的对比(面向索引)【面试题】
3、MySQL中的页
3.1 页的使用原因 3.2 页的结构
3.2.1 页文件头和页文件…目录
1、索引简介
1.1 什么是索引
1.2 使用索引的原因
2、索引中数据结构的设计 —— B树
2.1 哈希
2.2 二叉搜索树
2.3 B树 2.4 最终选择之——B树
2.4.1 B树与B树的对比(面向索引)【面试题】
3、MySQL中的页
3.1 页的使用原因 3.2 页的结构
3.2.1 页文件头和页文件尾 3.2.2 页主体
3.2.3 页目录
3.2.4 数据页头
4、B树在MySQL索引上的应用 4.1 三层树高的B树的数据存储量(理论上)
5、索引的分类
5.1 主键索引
5.2 普通索引
5.3 唯一索引
5.4 全文索引了解
5.5 聚集索引
5.6 二级索引/非聚集索引
5.7 索引覆盖 1、索引简介
1.1 什么是索引
MySQL中的索引是一种数据结构它可以高效快速的查询、更新相应数据大大的提高开发效率。索引通过⼀定的规则排列数据表中的记录使得对表的查询可以通过对索引的搜索来加快速度。
我们可以将索引理解为书中的目录可以根据目录快速的锁定到我们要阅读的页数。
1.2 使用索引的原因 数据库之所以叫数据库那么MySQL的设计必然需要满足两个需求
安全效率 显而易见使用索引的原因只有一个提高查询效率。 2、索引中数据结构的设计 —— B树 索引的出现就是为了提高查找效率那它底层到底使用的是哪种高效的数据结构呢让我们继续探索。
2.1 哈希
说到高效查找 相比大家第一个想到的就是哈希表因为它的时间复杂度可以达到O(1)级别可谓是极其高效正因为其高效的查找性能也使哈希成为最重要的数据结构没有之一。但是由于哈希只能一个数据一个数据的查找不具备范围查找的功能故索引并没有使用哈希作为它的底层结构。
2.2 二叉搜索树
二叉搜索树中序遍历得到的是一个有序序列这使得其具备范围查找的功能。
但是二叉搜索树在极端情况下可能为退化成一棵单分支树时间复杂度也会退化为O(N)。
并且在数据过多的情况下无法控住树高由于数据库上的数据是在磁盘上保存的而每访问一个节点都会发生一次磁盘IO磁盘的访问速度是很慢的所以当搜索二叉树出现单分支形态时将严重拉低数据库性能。 由此得出磁盘IO是制约数据库性能的主要因素。【拓展】 故索引也没有使用二叉搜索树作为它的底层结构。
2.3 B树
B树仍具备中序遍历序列有序的特点在B树中每个节点可以有多个子节点(可以超过2个)。对于N阶B树(度/阶)一般来说其子节点个数不可N个当插入的节点为第N个孩子时将开辟另一条分支。
由于其可以有多个孩子节点故其可以有效的控制树高时间复杂度也稳定为O(logN)这也意味着将会降低磁盘IO开销提升数据库性能。 2.4 最终选择之——B树
上面提到B树不仅可以满足数据库范围查询的要求而且可以降低IO开销但是开发数据库的大佬并没有将B树作为索引的底层结构因为他们发现了更加高效更加适合的数据结构——B树。
B树在满足B树可控树高、高效O(logN)查询、... 的优秀性能下进一步做了优化。
2.4.1 B树与B树的对比(面向索引)【面试题】 1.B树的叶子节点间使用单链表连接可以通过一个叶子节点找到它相邻的兄弟节点
且MySQL在组织叶子节点时使用的是双向循环链表
2.B树中所有节点的值都包含在了叶子节点中
在MySQL中非叶子节点只保留了对子结点的引用并不保存真实数据所有的真实数据都保存在叶子节点中。因此对于B树而言在相同树高的情况下查询任意元素的时间复杂度都是相同的性能均衡。 3、MySQL中的页
3.1 页的使用原因
MySQL中使用innodb存储引擎后生成的表空间文件后缀都为.ibd。而在.ibd文件中最重要的结构体就是页(Page)页是内存与磁盘交互的最小单元默认大小为16KB。
show variables like innodb_page_size; #查看页大小单位字节 每次内存与磁盘的交互至少读取一页所以在磁盘中每个页内部的地址都是连续的。之所以这样做有以下两点原因
时间局部性如果⼀个信息项正在被访问那么在近期它很可能还会被再 次访问空间局部性将来要使用的数据大概率与当前访问的数据在空间上是临近的
所以根据局部性原理 以⼀次从磁盘中读取一页的数据放入内存中当下次查询的数据还在这 个页中时就可以从内存中直接读取从而减少磁盘I/O提高性能。
注意即使一个页中没有数据也会使用16KB的存储空间。同时与索引的B树中的节点对应也就是说索引树中的每一个节点就对应一个页。 3.2 页的结构
在MySQL中有多种不同类型的页最常用的就是用来存储数据和索引的索引页也叫做数据 页但不论哪种类型的页都会包含页头(File Header)和页尾(File Trailer)页的主体信息使用数 据行进行填充。
每创建一个表生成一个保存数据的文件即.ibd文件也称为独立表空间文件。
上文说到一个.ibd文件中最重要的结构就是页接下来让我们一起探讨页的组成结构。 3.2.1 页文件头和页文件尾
页文件头和页文件尾中包含了当前文件的主要信息 这⾥我们只关注上一页页号和下一页页号通过这两个属性可以把页与页之间链接起来通过页号和页大小可以计算出上一页和下一页在磁盘上的偏移量形成⼀个双向循环链表。 3.2.2 页主体
页主体部分是保存真实数据的主要区域每当创建⼀个新页都会自动分配两个行。
⼀个是页内最小行 Infimun ⼀个是页内最大行 Supremun
这两个行并不存储任何真实信息而是作为数据行链表的头和尾。
并且每一个数据行有一个记录下一行的地址偏移量的区域next_record故此页内所有数据行组成了⼀个单向链表。 当向⼀个新页插入数据时将 Infimun 连接第一个数据行最后一行真实数据行连接 Supremun 这样数据行就构建成了一个单向链表更多的行数据插入后会按照主键从小到大的顺序进行链接自动排序。
也就是说所有数据行间形成单向链表最小化Infimun始终为链表的头最大行Supremun始终为链表的尾。
3.2.3 页目录
上文提到页中的每个数据行间形成了一个单向链表但是单链表的时间复杂度为O(N)无法满足高效查询为了提高查询效率InnoDB采用二分查找以加入页目录的结构来解决查询效率问题。
页目录实现形式将页内包括头行(最小行Infimun )、尾行(最大行Supremun )在内的所有行进行分组。具体实现如下
最小行单独为一组其他每个组最多8条数据超过8条数据时会开辟出一个新的分组最大行永远在最后一个分组中每创建一个分组页目录就会创建一个槽即槽的数量与组的数量是一致的且每个分组与槽都一一对应槽中记录了其对应分组的最后一条记录的地址同时记录这条记录的主键值 经过分组和槽的创建查找操作时就能够以二分查找性能快速定位到要目标数据大大提高了查找效率。
例如我们要查找某一条存在的记录
第一步通过索引树找到该记录所在页。第二步通过槽找到该记录所在分组。(每个槽都记录了该分组最后一条记录的主键值和地址因为页中所有数据行通过主键有序排列通过比较槽中的主键值可快速定位到目标记录所在分组)第三点遍历该分组的单链表(最多只有8条数据)查找成功。 注意页与页(节点与节点)间的遍历是从磁盘中加载数据的要想查询页中的的内容需要先通过磁盘IO把页从磁盘加载到内存中先加载后访问。 3.2.4 数据页头
数据页头记录了当前页保存数据相关的信息。 4、B树在MySQL索引上的应用
在索引的B树的叶子节点和非叶子节点中
非叶子节点和叶子节点均为页称为索引页/数据页。非叶子节点只记录索引信息。在索引页中保存的是主键值和叶子节点的引用。叶子节点存储的是真实的数据。数据页保存的是具体的数据。最后一层的叶子节点中页与页之间通过页号建立起关联关系(页号信息在页头中存储)最终形成了一个双向循环链表。 例如查找id为5的记录
判断B树根节点的索引记录57进入左孩子节点找到索引页2判断索引页2的索引记录找到与5相等的记录命中进入数据页3 故以上过程共经过3次IO过程加载索引页1--加载索引页2--加载数据页3 4.1 三层树高的B树的数据存储量(理论上)
上文已说明一个页的大小为16KB。
第一层根节点索引页
一个索引页存储的是主键值和子节点的引用。假设主键值占8Byte地址占6Byte故一条索引记录的大小为8614Byte。故一个索引页可保存16*1024/141170条索引记录。故B树的根节点可保存1170条索引记录即可指向1170个子节点。
第二层非叶子节点索引页
同样第二层的每个索引页可指向1170个子节点(数据页)。
第三层叶子结点数据页
算上页中页头、页尾、页主体....等结构空间的占比假设一个页中最多可以保存16条记录。故三层树高的B树一共可存储 1170*1170*1621,902,400条记录。
综上三层树高的B树一共可存储 1170*1170*1621,902,400条记录而在存储这么多数据的情况下只需要经过3次IO就可以查询到目标数据加载索引页1--加载索引页2--加载数据页3可以说是极其高效。
而且如果将索引页1、索引页2加载到内存中进行缓存那么只需一次IO就可以查询成功效率极高。 5、索引的分类
5.1 主键索引
主键索引也叫做聚集索引、聚簇索引当在表中定义一个主键(PRIMARY KEY)时将自动创建主键索引索引中的值就是主键列的值故推荐为每一个表定义一个主键。
5.2 普通索引
普通索引是需要手动创建的索引。最基本、最常用的索引类型没有唯一性限制。为了提升查询效率工作中通常为查询频繁的列创建索引。可以为多个列创建组合索引称为复合索引或组合索引。创建索引的前提是列的值重复性不高。例如gender(性别)列该列值要么为1(男)要么为2(女)就没有必要创建索引。创建索引之后都会生成一棵索引树创建多少索引就会生成多少棵索引树。 注意 创建索引所生成的索引树也是会占用磁盘空间的。 所以在创建索引时一定要慎重考虑需不需要创建。 索引树越多对增、删、改的效率影响越大将会拉低数据库性能。 所以没有必要创建冗余索引(如上文的gender列)。 5.3 唯一索引 当表中定义有UNIQUE唯一键时将自动创建唯一索引。 与普通索引类型但唯一索引的列不允许有重复值。
5.4 全文索引了解
基于文本列(CHAR、VARCHAR或TEXT列)上创建以加快对这些列中包含的数据查询和DML操作用于全文搜索仅MyISAM和InnoDB引擎支持。
5.5 聚集索引 即上文提到的主键索引。 如果表中没有定义主键(PRIMARY KEY)innoDB将使用第一个UNIQUE和NOT NULL的列作为聚集索引聚集索引可以标识数据行的唯一性 如果表中没有主键或者唯一非空列作为合适的聚集索引时innoDB会自动新增ROW_ID列ROW_ID单调递增并使用ROW_ID作为索引。ROW_ID为数据行中的隐藏列之一我们查询不到也使用不了
5.6 二级索引/非聚集索引
聚集索引以外的索引称为非聚集索引或二级索引二级索引中的每条记录都包含了该行的主键列默认包含的以及二级索引指定的列一列或多个列。要查询的列没有被索引完全包含索引中的列不够这时InnoDB通过二级索引的索引树查询到主键值再利用主键值通过主键索引树查询相关记录这个过程称为回表查询(普通索引树 -- 主键索引树)。如果要查询的列在二级索引中刚好就有二级索引包含了要查询的列那么此时不需要回表查询可以直接从二级索引树中把数据返回给用户这种情况称为索引覆盖。创建复合索引时如果name列在sn列的前面则使用where条件时也要先使用name再使用sn也不能只使用sn(使用AND时两列顺序不作要求)。如果只使用sn列那么索引失效(不走索引)。如果非要使用sn列来条件查询可以为sn单独创建一个索引。可以这样理解查字典时必须先找声母再找韵母而不能先找韵母再找声母。 5.7 索引覆盖
当一个select语句使用了普通索引且查询列表中的列刚好是创建普通索引时的所有或部分列这时就可以直接返回数据而不用回表查询这样的现象称为索引覆盖通过索引查找的列包含在索引中不需要回表查询这种情况就是索引覆盖。 END
