长沙公司网站开发,南宁百度做网站多少钱,wordpress functions.php 在哪,wordpress输入电子邮箱B树索引#xff08;索引的原理#xff09; 1.前言
前边我们详细唠叨了InnoDB数据⻚的7个组成部分#xff0c;知道了各个数据⻚可以组成⼀个双向链表#xff0c;⽽每个数据⻚中的记录会按照主键值从⼩到⼤的顺序组成⼀个单向链 表#xff0c;每个数据⻚都会为存储在它⾥边…
B树索引索引的原理 1.前言
前边我们详细唠叨了InnoDB数据⻚的7个组成部分知道了各个数据⻚可以组成⼀个双向链表⽽每个数据⻚中的记录会按照主键值从⼩到⼤的顺序组成⼀个单向链 表每个数据⻚都会为存储在它⾥边⼉的记录⽣成⼀个⻚⽬录在通过主键查找某条记录的时候可以在⻚⽬录中使⽤⼆分法快速定位到对应的槽然后再遍历该槽 对应分组中的记录即可快速找到指定的记录如果你对这段话有⼀丁点⼉疑惑那么接下来的部分不适合你返回去看⼀下数据⻚结构吧。⻚和记录的关系示 意图如下 2.没有索引的查找 2.1 在一个页中查找
以主键为搜索条件以其他列为搜索条件对⾮主键列的查找的过程可就不这么幸运了因为在数据⻚中并没有对⾮主键列建⽴所谓的⻚⽬录所以我们⽆法通过⼆分法快速定位相应的槽。这种情况下 只能从最⼩记录开始依次遍历单链表中的每条记录然后对⽐每条记录是不是符合搜索条件。很显然这种查找的效率是⾮常低的。 2.2 在很多个页中查找
在很多页的时候我们应该是先定位到对应的页然后到页中根据槽来查找。但是在没有索引的情况下由于我们并不能快速定位到记录所在的页所以只能从第一个页沿着链表遍历所有的页是不是超级超级蠢。 3.一个简单的索引方案
问题为什么我们要遍历所有的数据页拿
因为各个页之间没有规律我们并不知道怎么去匹配记录所以不得不遍历所有的数据页。如果我们想快速定位到需要查找的记录该怎么办其实参照记录目录的方法我们是不是也可以建立一个有序的的目录建立这个目录必须完成以下这些事
下一个页的记录主键值必须大于 上一个页记录的主键值页分裂一个页放不下的时候分成两个页时依旧要保证上面说的关系。 1准备工作
建表
mysql CREATE TABLE index_demo(- c1 INT,- c2 INT,- c3 CHAR(1),- PRIMARY KEY(c1)- ) ROW_FORMAT Compact;
Query OK, 0 rows affected (0.03 sec)插入数据
mysql INSERT INTO index_demo VALUES(1, 4, u), (3, 9, d), (5, 3, y);
Query OK, 3 rows affected (0.01 sec)
Records: 3 Duplicates: 0 Warnings: 0这时候的页如图所示 2插入数据测试
再插入一条记录
mysql INSERT INTO index_demo VALUES(4, 4, a);
Query OK, 1 row affected (0.00 sec)因为页10只能放3个记录所以我们不能不再分配一个页: 问题为什么页号不是连续的
新分配的数据页编号可能并不是连续的也就是我们使用的页空间上并不是连续的。它们只是通过维护上下页来建立链表关系。另外⻚10中⽤户记录最⼤的主键值是5⽽⻚28中有⼀条记录的主键值是4因为5 4所 以这就不符合下⼀个数据⻚中⽤户记录的主键值必须⼤于上⼀个⻚中⽤户记录的主键值的要求所以在插⼊主键值为4的记录的时候需要伴随着⼀次记录移动也 就是把主键值为5的记录移动到⻚28中然后再把主键值为4的记录插⼊到⻚10中这个过程的示意图如下 3) 给页建目录 以页28为例它对应目录项2这个目录项包含主键值页号。比方说我们想查找主键值为20的记录具体步骤粪两步
先从⽬录项中根据⼆分法快速确定出主键值为20的记录在⽬录项3中因为 12 20 209它对应的⻚是⻚9。再根据前边说的在⻚中查找记录的⽅式去⻚9中定位具体的记录。
记住这个目录有个别名就是索引哈哈 4. InnoDB的索引方案 4.1 上述的索引方案有什么问题
当表中数据不断增多的时候目录项非常耗费空间这对于记录数比较多的表不太现实我们时常会对记录做增删假设我们把页28中的记录全部删除了页28也就没有必要存在 同时目录项2也没有存在的必要了。
设计InnoDB的大叔们灵光乍现发现这些目录项其实和数据页长的差不多只不过目录项存储的列值时主键和页号所以他们复用了数据页的结构来存储目录项为了区分利用 头信息的record_type属性。 它的各个取值代表意思如下
0普通记录1目录项2最小记录3最大记录 4.2 最终实现的样子 从图中可以看出我们新分配了一个编号为30的页用来专门存储目录项记录。这里再次强调一遍 目录项记录和普通的 用户记录的不同点
目录项记录的record_type值是1而普通用户记录的record_type值是0。目录项记录只有主键值和页的编号两个列而普通的用户记录是用户自己定义的可能包含很多列另外还有InnoDB自己添加的隐藏列。还记得我们之前在唠叨记录头信息的时候说过一个 min_rec_mask的属性么只有在存储目录项的页中的**主键值的目录项记录的min_rec_mask值为1**其他都是0
假设我们按照某个主键20去查找记录大致步骤分以下几步
先看页的目录也就是30的页通过二分法这里指的是槽找到对应的目录项记录因为1220209所以定位到页9。再到页9中根据二分法快速定位到对应的用户记录。
问题虽然说目录项记录中只存储主键值和对应的页号比用户记录需要的空间存储小多了但是一个页也就16kb能存放的目录项记录也是有限的那如果表中的记录数据太多以至于一个数据页不足以存放所有的目录项记录该怎么办 4.3 当一个页目录不够的时候怎么办
当然是再准备一个目录页啦 为了⼤家更好的理解新分配⼀个⽬录项记录⻚的过程我们假设⼀个存储⽬录项记录的⻚最多只能存放4条⽬录项记录请 注意是假设哦真实情况下可以存放好多条的所以如果此时我们再向上图中插⼊⼀条主键值为320的⽤户记录的话那就需要分配⼀个新的存储⽬录项记录的⻚喽 从图中可以看出我们插入一个主键值为320的时候需要两个数据页
为存储该记录新增页31因为原先存储的目录项记录30已经满了所以新生成一个目录项页32
假设我们还是要查找主键为20的记录大致步骤分以下几步
确定目录项记录页先确定记录在哪个目录页内我们现在的存储⽬录项记录的⻚有两个即⻚30和⻚32⼜因为⻚30表示的⽬录项的主键值的范围是[1, 320)⻚32表示的⽬录项的主键值不⼩于320所以 主键值为20的记录对应的⽬录项记录在⻚30中。确定记录所在页确定真实记录在哪个页内在一个存储目录项记录的页中通过主键值二分法定位的一条目录项记录在数据页中查找主键为20的记录 4.4 当一层页目录越来越多时怎么办
问题如果数据量特别大目录页就会越来越多查询性能就会低下这时候怎么办
给页目录再生成一个目录就像这样 如图我们⽣成了⼀个存储更⾼级⽬录项的⻚33这个⻚中的两条记录分别代表⻚30和⻚32如果⽤户记录的主键值在[1, 320)之间则到⻚30中查找更详细的⽬ 录项记录如果主键值不⼩于320的话就到⻚32中查找更详细的⽬录项记录。
如果画的更加好一点最终的样子是这样的 这玩意是不是长得特别像倒过来的数呀上头是树根下头是树叶我们称之为 B数。
无论是存放用户记录的数据页还是存放目录像记录的数据页都放到这个B数结构中了所以我们都称之为节点。**从图中我们可以看出用户记录时存放到B树最底层的节点上我们称之为叶子节点。**其余用来存放目录项的节点称之为非叶子节点。
存储能力 4.5 常说的聚簇索引是什么
我们上边介绍的B树本身就是一个目录或者说本身就是一个索引它有两个特点
使用记录主键值的大小进行记录和页的排序这包括以下三个方面的含义 ⻚内的记录是按照主键的⼤⼩顺序排成⼀个单向链表。各个存放⽤户记录的⻚也是根据⻚中⽤户记录的主键⼤⼩顺序排成⼀个双向链表。存放⽬录项记录的⻚分为不同的层次在同⼀层次中的⻚也是根据⻚中⽬录项记录的主键⼤⼩顺序排成⼀个双向链表。 B树的叶子节点存储的是完整的用户记录这个记录中存储了所有列的值
我们把具有这两种特性B树称之为聚簇索引 。所有完整的⽤户记录都存放在这个聚簇索引的叶⼦节点处。这种聚簇索引并不需要我们在MySQL语句中显式的使⽤INDEX 语句去创建后边会介绍索引相关的语句InnoDB存储引擎会⾃动的为我们创建聚簇索引。另外有趣的⼀点是在InnoDB存储引擎中聚簇索引就是数据的存储 ⽅式所有的⽤户记录都存储在了叶⼦节点也就是所谓的索引即数据数据即索引。 4.6 二级索引
问题上面所说的索引都是围绕主键建立的当搜索条件是其他列怎么办
我们可以多建⼏棵B树不同的B树中的数据采⽤不同的排序规则。⽐⽅说我们⽤c2列的⼤⼩作为数据⻚、⻚中记录的排序规则再建⼀棵B树效果如下 图所示 这个B树与上面说的聚簇索引有几处不同
页内使用记录c2列的大小顺序成一个单链表各个存放⽤户记录的⻚也是根据⻚中记录的c2列列⼤⼩顺序排成⼀个双向链表。存放⽬录项记录的⻚分为不同的层次在同⼀层次中的⻚也是根据⻚中⽬录项记录的c2列⼤⼩顺序排成⼀个双向链表。B树的叶子节点存储的并不是完整的用户记录而只是c2列主键这两个列的值。目录像记录中也不再是主键页号的搭配而变成了c2列页号的搭配。
假设我们现在想通过c2列为4的记录为例查找过程如下
根据最高层级的页44确定下一级的目录页42因为249根据页42可以找到真实数据所在的页在页42中可以快速定位到实际存储用户记录的页但是由于c2列并没有唯一性约束所以c2列值为4的记录可能分布在多个数据页中又因为244,所以可以确定用户记录存放到页34和页35到真实页之后再通过二分法槽找到具体的记录最重要的一步二级索引的就是回表根据主键再去聚簇索引中查找一遍完整的用户记录
问题为什么用回表操作不是将数据存储到叶子节点那
如果把完整的⽤户记录放到叶⼦节点是可以不⽤回表但是太占地 ⽅了呀相当于每建⽴⼀棵B树都需要把所有的⽤户记录再都拷⻉⼀遍这就有点太浪费存储空间了。因为这种按照⾮主键列建⽴的B树需要⼀次回表操作才可以 定位到完整的⽤户记录所以这种B树也被称为⼆级索引英⽂名secondary index或者辅助索引。由于我们使⽤的是c2列的⼤⼩作为B树的排序规则所以 我们也称这个B树为为c2列建⽴的索引。 4.7 联合索引
我们也可以同时以多个列的大小作为排序规则建立索引比方说我们想让B树按照c2和c3列的大小进行排序这个包含两层含义
先把各个记录和页按照c2列排序在c2列相同的情况下采用c3列进行排序
为c2列和c3列建立的索引的示意图如图 如图所示我们 需要注意以下几点
每个目录项记录都是由c2、c3和页号组成各条记录先按照c2排序再按照c3排序叶子节点是由c2、c3和主键c1组成。
其实本质也是个二级索引只是无论目录项记录还是数据页记录多了个列而已。 5.InnoDB索引细节 5.1 索引的生成过程 比较重要
每当为某个表创建一个B树索引的时候就会为这个索引创建一个根节点页面。最开始既没有目录页也没有数据页。随后向表中插入数据时先把用户记录存储到根节点中。继续向根节点插入数据后此时根节点的数据会复制到一个新的页比如页a,然后对这个页做页分裂得到一个新页比如页b。往后新插入的数据就会放到a或者b中根节点就升级成了目录页
一个b树索引的根节点自诞生之日后就不会再移动。这样只要我们对某个表建⽴⼀个索引那么它的根节点的⻚号便会被记录 到某个地⽅然后凡是InnoDB存储引擎需要⽤到这个索引的时候都会从那个固定的地⽅取出根节点的⻚号从⽽来访问这个索引。 ⼩贴⼠ 跟⼤家剧透⼀下这个存储某个索引的根节点在哪个⻚⾯中的信息就是传说中的数据字典中的⼀项信息关于更多数据字典的内容 后边会详细唠叨别着急哈。 5.2 非唯一二级索引
如果我们的数据是这样的 如果二级索引中目录项记录的内容只是索引列页号的话那么图示 这时候如果我们想插入一行记录9,1,‘c’,那么这个时候遇到一个很大的问题这时候这条记录是插到页4还是页5那
为了能够让插入的记录能找到自己所在的页**我们需要保证B树同一层节点的目录项记录除了页号以外这条记录是唯一的。**所以这时候我们需要再加入一个列主键。
也就是我们把主键值也添加到⼆级索引内节点中的⽬录项记录了这样就能保证B树每⼀层节点中各条⽬录项记录除⻚号这个字段外是唯⼀的所以我们为c2列建 ⽴⼆级索引后的示意图实际上应该是这样⼦的 这时候当我们想插入一条9,1,‘c’时先比较c2列如果c2列是一样的再比较主键列主键列肯定是不一样的97,所以新纪录应该被插入到页5中。 6.总结 6.1 如果没有索引的查找会是很恐怖的无论是在一个页还是多个页中查找基本都是遍历的逻辑。 6.2 当我们想通过建立一个类似书籍目录一样的结构来索引数据页的时候会存在很多问题比如耗空间、多一种设计实现方式 6.3 最终我们通过复用数据页的结构来索引数据页这个叫做目录页目录页的主要作用就是索引页 6.4 不同的索引具体实现方式
聚簇索引数据页主键用户记录目录页主键页号二级唯一索引数据页排序列主键目录页排序列主键二级非唯一索引数据页排序列主键目录页排序列主键页号 非唯一的话目录页多个主键列联合索引数据页排序列1排序列2主键目录页排序列1排序列2页号 6.5索引的生成方式
参照 5.1结束peace
