网站地图1 500 怎么做,百度服务中心电话,怎么在拼多多卖东西,国防科技大学录取分数线目录
1 简介
1.1 索引是什么
1.2 为什么要使用索引
2 索引应该选择哪种数据结构
2.1 HASH
2.2 二叉搜索树
2.3 N叉树#xff08;B树#xff09;
2.4 B树
3 MySQL的页
3.1 为什么要使用页
3.2 页文件头和页文件尾
3.3 页主体
3.4 页目录
4 B树在MySQL索引中的应…目录
1 简介
1.1 索引是什么
1.2 为什么要使用索引
2 索引应该选择哪种数据结构
2.1 HASH
2.2 二叉搜索树
2.3 N叉树B树
2.4 B树
3 MySQL的页
3.1 为什么要使用页
3.2 页文件头和页文件尾
3.3 页主体
3.4 页目录
4 B树在MySQL索引中的应用
5 索引分类
5.1 主键索引
5.2 普通索引
5.3 唯一索引
5.4 全文索引
5.5 聚集索引
5.6 非聚集索引
5.7 索引覆盖 1 简介
1.1 索引是什么 MySQL的索引是一种数据结构它可以帮助数据库高效地查询、更新数据表中的数据。索引通过一定的规则排列数据表中的记录使得对表的查询可以通过对索引的搜索来加快速度。 MySQL索引类似于书籍的目录通过指向数据行的位置可以高速定位和访问表中的数据比如汉语字典中的目录索引页我们可以按笔画、偏旁部首、拼音等排序的目录索引快速查找到需要的字。
1.2 为什么要使用索引 显而易见使用索引的目的只有一个就算提升数据检索的效率在应用程序运行的过程中查询操作的频率远远高于增删查改的频率。 2 索引应该选择哪种数据结构
2.1 HASH
时间复杂度O1 是最重要的数据结构没有之一。 缺点不支持范围查找。 MySQL没有采用此数据结构。 2.2 二叉搜索树
中序遍历是一个有序序列---支持范围查找
时间复杂度O(n) 缺点 节点个数过多时无法保证树高。 由于数据库上的数据都是在磁盘中保存的每一次访问子节点都会都会发生一次磁盘IO 磁盘IO是制约数据库性能的主要因素。 因此数据库没有采用二叉搜索树的数据结构。 2.3 N叉树B树 N叉树每个节点都可以有超过两个的子节点可以解决树高问题。
时间复杂度OlogN
在数据量相同的情况下可以有效控制树高也就是可以使用更少的IO找到目标节点从而提高数据库的效率。
然而MySQL并没有采用此数据结构。
2.4 B树 B树是一种经常用于数据库和文件系统等场合的平衡查找树是MySQL索引采用的数据结构以三阶B树为例如下图所示 时间复杂度OlogN 优点可以有效控制树高 B树与B树对比 1.叶子节点之间有一个相互连接的引用可以通过一个叶子节点找到它相信的兄弟节点。 MySQL在组织叶子节点时使用的是双向链表。 2.非叶子节点的值都保存在叶子节点中。 MySQL非叶子节点只保存了对叶子节点的引用没有保存真实的数据所有真实的数据都保存在叶子节点中。 3.对于B树而言在相同树高的情况下查找任一元素的时间复杂度都一样性能均衡。 3 MySQL的页
3.1 为什么要使用页 在.ibd文件中最重要的结构体就是Page页页是内存与磁盘交互的最小单元默认大小为16KB,每次内存与磁盘的交互至少读取一页所以在磁盘中每个页内部的地址都是连续的之所以这样做是因为在使用数据的过程中根据局部性原理将来要使用的数据大概率与当前访问的数据在空间上是临近的所以一次从磁盘中读取一页的数据放入内存中当下次查询的数据还在这个页中时就可以从内存中直接读取从而减少磁盘I/O提高性能。 MySQL每创建一张表就会生成一个.ibd文件。这个.ibd文件被称为独立表空间文件。 MySQL中有很多页类型这里只讨论数据页或者叫做索引页
3.2 页文件头和页文件尾
页文件头和页文件尾中包含的信息如下图所示 这里我们只关注上一页页号和下一页页号通过这两个属性可以把页与页之间链接起来形成一个双向链表。 通过页号和页大小可以计算出下一页和上一页在磁盘上的偏移量或者叫地址 3.3 页主体 页主体部分是保存真实数据的主要区域每当创建一个新页都会自动分配两个行一个是页内最小行Infimun,另一个是页内最大行Supermun。这两个行并不存储任何真实信息而是作为数据行链表的头和尾第一个数据行有一个记录下一行的地址偏移量的区域next_record将页内所有数据行组成一个单向链表此时新页的结构如下图所示 当向一个新页插入数据时将Infimun连接第一个数据行最后一行真实数据行连接Supermun这样数据行就构建成了一个单向链表更多的行数据插入后会按照主键从小到大的顺序进行链接如下图所示 3.4 页目录 分组数据行的的分组每个分组最多可以容纳8条记录超过8条记录时会分裂出来一个新的组。 注意最小行单独为一个组最大行永远在最后一个组。 创建分组时会在页目录中创建一个槽槽的数量与分组的数量一致槽会指定对应分组的最后条记录同时保存这条记录的主键值。 查询某条记录的步骤
1.首先要找到这个记录所在的页
2.在页中找到所在的槽
3.在分组中找到对应的记录
4 B树在MySQL索引中的应用
非叶子节点保存索引数据叶子节点保存真实数据如下图所示 以查找id为5的记录完整的检索过程如下
1.首先判断B树的根节点中的索引记录此时57应访问左孩子节点找到索引页2.
2.在索引页2中判定id大小找到与5对等的记录命中 以上的IO过程加载索引页1 --加载索引页2 --加载数据页3 共三次IO 5 索引分类
5.1 主键索引 当在一个表上定义一个主键时该表会自动创建索引索引的值是主键列的值InnoDB使用它作为聚集索引或者叫聚簇索引。 推荐为每个表定义一个主键。如果没有逻辑上唯一且非空的列或列集可以使用主键则添加一个自增列。 5.2 普通索引 最基本的索引类型没有唯一性的限制。 可能为多列创建组合索引称为复合索引或组全索引 5.3 唯一索引 当在一个表上定义一个唯一键UNIQUE时自动创建唯一索引。 与普通索引类似但区别在于唯一索引的列不允许有重复值。 5.4 全文索引 基于文本列CHAR、VARCHAR或TEXT列上创建以加快对这些列中包含的数据查询和DML操作 用于全文搜索仅MyISAM和InnoDB引擎支持。 5.5 聚集索引 与主键索引是同义词。 如果没有为表定义PRIMARY KEYInnoDB使用第一个UNIQUE和NOT NULL的列作为聚集索引。 如果表中没有PRIMARY KEY或合适的UNIQUE索引InnoDB会为新插入的行生成一个行号并用6字节的ROW_ID字段记录ROW_ID单调递增并使用ROW_ID作为索引。 ROW_ID是数据行中的一个隐藏列之一 5.6 非聚集索引 聚集索引以外的索引称为非聚集索引或二级索引。 二级索引中的每条记录都包含该列的主键列以及二级索引指定的列。 InnoDB使用这个主键值来搜索聚集索引中的行这个过程称为回表查询。 5.7 索引覆盖 当一个select语句使用了普通索引且查询列表中的列刚好是创建普通索引时的所有或部分列这时就可以直接返回数据而不用回表查询这样的现象称为索引覆盖。 完
如果哪里有疑问的话欢迎来评论区指出和讨论如果觉得文章有价值的话就请给我点个关注还有免费的收藏和赞吧谢谢大家
