不懂数据库索引的底层原理?那是因为你心里没点b树

  • 时间:
  • 浏览:65
  • 来源:梦城博客 - 专注共享啊啊博客技术

  B-Tree和B+Tree该要怎样选着呢?也有有哪些优劣呢?

  1、B-Tree机会非叶子结点也保存具体数据,全都在查找某个关键字的以后 找到即可返回。而B+Tree所有的数据也有叶子结点,每次查找都得到叶子结点。全都在同样深度的B-Tree和B+Tree中,B-Tree查找某个关键字的速率单位更高。

  2、机会B+Tree所有的数据也有叶子结点,为社 让结点之间有指针连接,在找大于某个关键字机会小于某个关键字的数据的以后 ,B+Tree只都要找到该关键字为社 让沿着链表遍历就并能了,而B-Tree还都要遍历该关键字结点的根结点去搜索。

  3、机会B-Tree的每个结点(这里的结点并能理解为原先数据页)都存储主键+实际数据,而B+Tree非叶子结点只存储关键字信息,而每个页的大小有限是有限的,全都同一页能存储的B-Tree的数据会比B+Tree存储的更少。原先同样总量的数据,B-Tree的深度会更大,增大查询时的磁盘I/O次数,进而影响查询速率单位。

  鉴于以上的比较,全都在常用的关系型数据库中,也有选着B+Tree的数据行态来存储数据!下面大伙儿以mysql的innodb存储引擎为例讲解,全都累似 sqlserver、oracle的原理累似 !

  这颗矮胖的树只是我我B-Tree,注意里边是杠精的杠而也有减,全都只是我我要读成B减Tree了~

  大伙儿仔细对比于B-Tree的图能发现有哪些不同?

  1、非叶子结点上机会并能key信息了,满足里边第1点行态!

  2、所有叶子结点下面也有原先data区域,满足里边第2点行态!

  3、非叶子结点的数据在叶子结点上都能找到,如根结点的元素4、8在最底层的叶子结点上并能找到,满足里边第3点行态!

  4、注意图中叶子结点之间的箭头,满足满足里边第4点行态!

  前面关于数据存储的也有演示的聚集索引的实现,机会里边的用户表都要以“用户名字”建立原先非聚集索引,是为社 会 实现的呢?大伙儿看下图:

  原先们常用的数据库的索引底层的原先数据行态是有哪些样的呢?想到这里我又回到图书馆借了一本《数据库从入门到放弃》!

  并能 ,你否有对B-Tree的几点行态都清晰了呢?在二叉树中,每个结点并能原先元素。为社 让在B-Tree中,每个结点都机会含有多个元素,为社 让非叶子结点在元素的左右也有指向子结点的指针。

  随着数据的不断写入,这棵树也逐渐枝繁叶茂,如下图

  全都这里就不一一列举了!那看一遍这篇文章,大伙儿并能带着问题图片去分析一下为有哪些要有有有哪些建议?为有哪些like的模糊查询以%开头,会原困索引失效?为有哪些原先表建的索引尽量不言而喻超过三个小?为有哪些? 为有哪些??为有哪些???相信看一遍这里的你再去掉 当时人的全都思考应该有答案了吧?

  并能 大的图书馆,我为有哪些能在并能 短的时间内找到我不需要 的书?机会有有哪些书是杂乱无章的堆放,机会并能 任何标识的放上去书架,我还并能 快的找到吗?

  这棵树的非叶子结点上存的也有主键,那机会原先表并能 主键会为社 会 样?在innodb中,机会原先表并能 主键,那默认会找建了唯一索引的列,机会只是我我能 ,则会生成原先隐形的字段作为主键!

  这不禁给你不需要 到了大伙儿开发中用到的数据库,图书馆的书就累似 大伙儿数据表中的数据,楼层索引牌、书架分类标识、索书号就累似 大伙儿查找数据的索引。

  也只是我我说innodb引擎数据在物理上是按主键顺序存放,而MyISAM引擎数据在物理上按插入的顺序存放。为社 让MyISAM的叶子结点不存放数据,全都非聚集索引的存储行态与聚集索引累似 ,在使用非聚集索引查找数据的以后 通过非聚集索引树就能直接找到数据的地址了,不都要回表,这比innodb的搜索速率单位会更高呢!

  

  B+Tree是在B-Tree基础上的五种优化,使其更适合实现外存储索引行态。B+Tree与B-Tree的行态很像,为社 让也有几块当时人的行态:

  2、原先Page1有10条数据,在插入第11条数据的以后 进行裂变,根据前面对B-Tree、B+Tree行态的了解,那这离米 是一颗11阶的树,裂变以后 每个结点的元素离米 为11/2=三个小,那是也有应该页裂变以后 主键1-5的数据还是在原先的页,主键6-11的数据会放上去新的页,根结点存放主键6?

  机会是原先得话新的页空间利用率并能80%,为社 让会原困更为频繁的页分裂。全都innodb对你这种 点做了优化,新的数据放上去新创建的页,不移动原有页面的任何记录。

  左边淡蓝色区域称为Page Directory,这块区域由多个slot组成,是原先稀疏索引行态,即原先槽中机会属于多个记录,离米 属于4条记录,最多属于8条记录。槽内的数据是有序存放的,全都当大伙儿寻找三根数据的以后 并能先在槽中通过二分法查找到原先大致的位置。

  图中的有有哪些名字均来源于网络,希望并能 误伤正在看这篇文章的你~^_^

  要了解数据库索引的底层原理,大伙儿就得先了解五种叫树的数据行态,而树中很经典的五种数据行态只是我我二叉树!全都下面大伙儿就从二叉树到平衡二叉树,再到B-树,最后到B+树来一步一步了解数据库索引底层的原理!

1、主键索引树的叶子结点的数据区域并能 存放实际的数据,存放的是数据记录的地址。

2、数据的存储也有按主键顺序存放的,按写入的顺序存放。

  那机会按照[12 27 29 35 38 48 55]的顺序插入一颗平衡二叉树,会为社 会 样呢?大伙儿看看插入以及平衡的过程:

  每次新增数据,也有将原先页写满,为社 让新创建原先页继续写,这里觉得是有个隐含条件的,那只是我我主键自增!主键自增写入时新插入的数据不需要影响到原有页,插入速率单位高!且页的利用率高!为社 让机会主键是无序的机会随机的,那每次的插入机会会原困原有页频繁的分裂,影响插入速率单位!降低页的利用率!这也是为有哪些在innodb中建议设置主键自增的原困!

  右边区域为数据区域,每原先数据页中都含有多条行数据。注意看图中最里边和最下面的两条特殊的行记录Infimum和Supremum,这是原先虚拟的行记录。在并能 全都用户数据的以后 Infimum的下三根记录的指针指向Supremum,当有用户数据的以后 ,Infimum的下三根记录的指针指向当前页中最小的用户记录,当前页中最大的用户记录的下三根记录的指针指向Supremum,至此整个页内的所有行记录形成原先单向链表。

  为社 让机会同样是里边那一组数,大伙儿当时人升序排列后再插入,也只是我我说按照[12 27 29 35 38 48 55]的顺序插入,会为社 会 样呢?

  我到楼上后又看一遍每排的书架上又对书的分类进行了细分,原先我不需要 调快的定位到我不需要 找的书具体在哪个书架!

  非聚集索引的存储行态与前面是一样的,不同的是在叶子结点的数据偏离 存的不再是具体的数据,而数据的聚集索引的key。全都通过非聚集索引查找的过程是先找到该索引key对应的聚集索引的key,为社 让再拿聚集索引的key到主键索引树上查找对应的数据,你这种 过程称为回表

  在讲你这种 种数据行态在数据库中的选着以后 ,大伙儿还都要了解的原先知识点是操作系统从磁盘读取数据到内存是以磁盘块(block)为基本单位的,位于同原先磁盘块中的数据会被一次性读取出来,而也有都要有哪些取有哪些。即使只都要原先字节,磁盘也会从你这种 位置日后刚开始,顺序向后读取一定长度的数据放上去内存。原先做的理论最好的法子是计算机科学中著名的局部性原理: 当原先数据被用到时,其附过的数据也通常会马上被使用。

  预读的长度一般为页(page)的整倍数。页是计算机管理存储器的逻辑块,硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储块称为一页(在全都操作系统中,页得大小通常为4k)。

1、找到数据所在的页。你这种 查找过程就跟前面说到的B+Tree的搜索过程是一样的,从根结点日后刚开始查找无缘无故 到叶子结点。

2、在页内找具体的数据。读取第1步找到的叶子结点数据到内存中,为社 让通过分块查找的最好的法子找到具体的数据。

  机会数据还比较少,原先页就能容下,全都并能原先根结点,主键和数据也也有保位于根结点(左边的数字代表主键,右边名字、性别代表具体的数据)。假设大伙儿写入10条数据以后 ,Page1满了,再写入新的数据会为社 会 存放呢?大伙儿继续看下图

  为社 让每个楼层也有一台查询终端,输入书名就能查到对应的唯一标识“索书号”,累似 于P159-49/164原先的原先编码,书架上的书也有按照你这种 编码进行排序的!有了你这种 编码再去对应的书架上,调快就能找到对应的书在书架的具体位置了。

它的左右原先子树的深度差的绝对值不超过1,为社 让左右原先子树也有一棵平衡二叉树。

  大伙儿也看一遍了前面[35 27 48 12 29 38 55]插入完成后的图,觉得就机会是一颗平衡二叉树啦。

  那B-Tree有有哪些行态呢?一棵m阶的B-Tree有如下行态:

  机会都要查找原先元素,那流程是为社 会 样的呢?大伙儿看下图,机会大伙儿要在下面的B-Tree中找到关键字24,那流程如下







  前几天下班回到家后正在补救原先白天没补救的bug,厕所无缘无故 传来对象的声音:

  对象:xx,你有《时间简史》吗?

  我:我去!妹子,你这啥癖好啊,我有时间只是我我会去捡屎啊!

  对象:...人家说的是霍金的科普著作《时间简史》,是一本书啦!

  我:哦,原先并能 ...

  对象:人家看一遍诶,你明天我不需要 去图书馆借一本吧...

  我:我明天都要改...

  对象:你是也有不爱我了,分手!

  我:我一大早就去~

本文在当时人技术博客不同步发布,详情可用力戳

亦可扫描屏幕右侧二维码关注当时人公众号,公众号内有当时人联系最好的法子,等你来撩...

  普通的B-Tree的结点中,元素只是我我原先个的数字。为社 让上图中,大伙儿把元素偏离 拆分成了key-data的形式,key只是我我数据的主键,data只是我我具体的数据。原先大伙儿在找三根数的以后 ,就沿着根结点往下找就ok了,速率单位是比较高的。

  每个行记录的也有原先n_owned的区域(图中粉红色区域),n_owned标识你这种 你这种 块有几块条数据,伪记录Infimum的n_owned值无缘无故 1,记录Supremum的n_owned的取值范围为[1,8],全都用户记录n_owned的取值范围[4,8],为社 让并能每个块中最大的那条记录的n_owned才会有值,全都的用户记录的n_owned为0。

  前面对B-Tree操作的图大伙儿能看出来,元素只是我我累似 1、2、3原先的数值,为社 让数据库的数据也有三根条的数据,机会某个数据库以B-Tree的数据行态存储数据,那数据为社 会 存放的呢?大伙儿看下一张图

1、产生新的Page2,为社 让将Page1的内容克隆到Page2。

2、产生新的Page3,“秦寿生”的数据放上去Page3。

3、原先的Page1依然作为根结点,为社 让变成了原先不存放数据只存放索引的页,为社 让有原先子结点Page2、Page3。













  机会里边B-Tree的图变成B+Tree,那应该如下:

  机会是升序插入,新插入的数据无缘无故 比已位于的结点数据也有大,全都每次也有往结点的右边插入,最终原困这棵树严重偏科!!!上图只是我我最坏的状况,也只是我我一棵树退化为原先线性链表了,原先查找速率单位自然就低了,完整篇 并能 发挥树的优势了呢!

为了较大发挥二叉树的查找速率单位,让二叉树不再偏科,保持各科平衡,全都有了平衡二叉树!

  好了,这只是我我一棵二叉树啦!大伙儿能看一遍,经通过一系列的插入操作以后 ,原先无序的一组数机会变成原先有序的行态了,为社 给你这种 树满足了里边提到的原先二叉树的行态!













  有数据插入那也有删除,机会你这种 用户表频繁的插入和删除,那会原困数据页产生碎片,页的空间利用率低,也有原困树变的“虚高”,降低查询速率单位!这并能通过索引重建来消除碎片提高查询速率单位!

  行记录被Page Directory逻辑的分成了多个块,块与块之间是有序的,也只是我我说“4”你这种 槽指向的数据块内最大的行记录的主键也有比“8”你这种 槽指向的数据块内最小的行记录的主键要小。为社 让块内控 的行记录不一定有序。

  这跟大伙儿在新华字典中找某个汉字是一样的,先通过字典的索引定位到该汉字拼音所在的页,为社 让到指定的页找到具体的汉字。innodb中定位到页后用了哪种策略快速查找某个主键呢?这大伙儿就都要从页行态日后刚开始了解。

  从你这种 流程大伙儿能看出,B-Tree的查询速率单位好像全都言而喻比平衡二叉树高。为社 让查询所经过的结点数量要少全都,也就原困着要少全都次的磁盘IO,这对

性能的提升是很大的。

  上图为MyISAM主键索引的存储行态,大伙儿能看一遍的不同是

  

  数据插入了为社 会 查找呢?

  第二天 一大早给你到了图书馆,刚进门看一遍一遍原先索引牌,标识着不同楼层的功能,原先我调快能定位到我不需要 找的目标所在的楼层了。

1、like的模糊查询以%开头,会原困索引失效。

2、原先表建的索引尽量不言而喻超过三个小。

3、尽量使用覆盖索引。

4、尽量不言而喻在重复数据多的列上建索引。

5、。。。。。。。。。。。

6、。。。。。。。。。。。

  一颗平衡二叉树能容纳几块的结点呢?这跟树的深度是有关系的,假设树的深度为h,那每一层最多容纳的结点数量为2^(n-1),整棵树最多容纳节点数为2^0+2^1+2^2+...+2^(h-1)。原先计算,80w数据树的深度离米 在20左右,那也只是我我说从有着80w条数据的平衡二叉树中找原先数据,最坏的状况下都要20次查找。机会是内存操作,速率单位也是很高的!为社 让大伙儿数据库中的数据基本也有放上去磁盘中的,每读取原先二叉树的结点只是我我一次磁盘IO,原先大伙儿找三根数据机会要经过20次磁盘的IO?那性能就成了原先很大的问题图片了!原先们是也有并能把这棵树压缩一下,让每一层并能容纳更多的节点呢?觉得我矮,为社 给你胖啊...

  光看概念很重枯燥,假设大伙儿现在有原先一组数[35 27 48 12 29 38 55],顺序的插入到原先数的行态中,步骤如下













  并能十分钟,给你从图书馆借好书出来了。

  里边包括存储和搜索也有拿的innodb引擎为例,那MyISAM与innodb在存储上有啥不同呢?憋缩话,看图:

  这里都要注意的全都是,在某个页内插入新行时,为了不减少数据的移动,通常是插入到当前行的里边机会是已删除行留下来的空间,全都在某原先页内的数据并也有完整篇 有序的(里边页行态偏离 有细讲),为社 让为了为了数据访问顺序性,在每个记录中也有原先指向下三根记录的指针,以此构成了三根单向有序链表,不过在这里为了方便演示我是按顺序排列的!

1、所有的非叶子节点只存储关键字信息。

2、所有卫星数据(具体数据)都位于叶子结点中。

3、所有的叶子结点含有有了完整篇 元素的信息。

4、所有叶子节点之间也有原先链指针。

  这里有原先问题图片都要注意的是

  1、为有哪些要克隆Page1为Page2而也有创建原先新的页作为根结点,原先就少了一步克隆的开销了?

  机会是重新创建根结点,那根结点存储的物理地址机会无缘无故 会变,不有利于查找。为社 让在innodb中根结点是会预读到内存中的,全都结点的物理地址固定会比较好!

  全都当大伙儿要找主键为6的记录时,先通过二分法稀疏索引中找到对应的槽,也只是我我Page Directory中“8”你这种 槽,“8”你这种 槽指向的是该数据块中最大的记录,而数据是单向链表行态全都无法逆向查找,全都都要找到上原先槽即“4”你这种 槽,为社 让通过“4”你这种 槽中最大的用户记录的指针沿着链表顺序查找到目标记录。

  在InnoDB存储引擎中,也有页的概念,默认每个页的大小为16K,也只是我我每次读取数据时也有读取4*4k的大小!假设大伙儿现在有原先用户表,大伙儿往里边写数据

  二叉树是每个结点最多有原先子树的树行态。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。二叉树有如下行态:

  这棵树始终满足平衡二叉树的几块行态而保持平衡!原先大伙儿的树只是我我会退化为线性链表了!大伙儿都要查找原先数的以后 就能沿着树根无缘无故 往下找,原先的查找速率单位和二分法查找是一样的呢!

  有个叫“秦寿生”的大伙儿来了,为社 让Page1机会放不下数据了,这以后 就都要进行页分裂,产生原先新的Page。在innodb中的流程是为社 会 样的呢?

1、每个结点都含有原先元素以及n个子树,这里0≤n≤2。

2、左子树和右子树是有顺序的,次序并能任意颠倒。左子树的值要小于父结点,右子树的值要大于父结点。

1、每个结点最多m个子结点。

2、除了根结点和叶子结点外,每个结点离米 有m/2(向上取整)个子结点。

3、机会根结点也有叶子结点,那根结点离米 含有原先子结点。

4、所有的叶子结点都位于同一层。

5、每个结点都含有k个元素(关键字),这里m/2≤k<m,这里m/2向下取整。

6、每个节点中的元素(关键字)从小到大排列。

7、每个元素(关键字)字左结点的值,都小于或等于该元素(关键字)。右结点的值都大于或等于该元素(关键字)。

  是也有感觉跟丈母娘张口他不知道要彩礼一样,列一堆的条件,为社 让每三根都给你很懵逼!下面大伙儿以原先[0,1,2,3,4,5,6,7]的数组插入一颗3阶的B-Tree为例,将所有的条件都串起来,你就明白了!

  平衡二叉树是五种特殊的二叉树,全都他也满足前面说到的二叉树的原先行态,一起还有原先行态:

  大伙儿无缘无故 会在全都的文章或书中能看一遍全都索引的使用建议,比如说