因戈尔斯cba

admin · 2009-07-01

  

  本文转载自微信民众号「小林coding」,作家小林coding 。转载本文请干系小林coding民众号。

  群众好,我是小林。

  群众背陈腔滥调文的期间,都理解 MySQL 里 InnoDB 存储引擎是采取 B+ 树来构制数据的。

  这点没错,可是群众理解 B+ 树里的节点里寄存的是甚么呢?盘查数据的经过又是如何的?

  这回,咱们从数据页的角度看 B+ 树,看看每一个节点长啥样。

  

   InnoDB 是奈何存储数据的?

  MySQL 援救众种存储引擎,区别的存储引擎,存储数据的方法也是区别的,咱们最常操纵的是 InnoDB 存储引擎,以是就跟群众图解下InnoDB 是奈何存储数据的。

  记载是依照行来存储的,可是数据库的读取并不以「行」为单元,不然一次读取(也便是一次 I/O 操纵)只可收拾一行数据,效力会分外低。

  因而,InnoDB 的数据是按「数据页」为单元来读写的,也便是说,当必要读一笔记录的期间,并非将这个记载自身从磁盘读出来,而是以页为单元,将其完全读入内存。

  数据库的 I/O 操纵的最小单元是页,InnoDB 数据页的默许巨细是 16KB,象征着数据库每次读写都是以 16KB 为单元的,一次起码从磁盘中读取 16K 的实质到内存中,一次起码把内存中的 16K 实质改正到磁盘中。

  数据页囊括七个局限,组织如下图:

  

  这 7 个局限的效率如下图:

  

  正在 File Header 中有两个指针,判袂指向上一个数据页和下一个数据页,衔接起来的页相称于一个双向的链外,如下图所示:

  

  采取链外的组织是让数据页之间不需假使物理上的相联的,而是逻辑上的相联。

  数据页的紧要效率是存储记载,也便是数据库的数据,以是重心说一下数据页中的 User Records 是怎样构制数据的。

  数据页中的记载依照「主键」秩序构成单向链外,单向链外的特征便是拔出、删除分外便利,可是检索效力不高,最差的景况下必要遍历链外上的全数节点能力杀青检索。

  因而,数据页中有一个页目次,起到记载的索引效率,就像咱们书那样,针对书中实质的每一个章节设立了一个目次,思看某个章节的期间,能够检查目次,神速找到对应的章节的页数,而数据页中的页目次便是为了能神速找到记载。

  那 InnoDB 是奈何给记载创修页目次的呢?页目次与记载的瓜葛如下图:

  

  页目次创修的经过如下:

   将全数的记载分别成几个组,这些记载囊括最小记载和最大记载,但不囊括标帜为已删除的记载; 每一个记载组的末了一笔记录便是组内最大的那笔记录,而且末了一笔记录的头讯息中会存储该组一共有若干笔记录,行为 n_owned 字段(上图中粉赤色字段) 页目次用来存储每组末了一笔记录的地点偏移量,这些地点偏移量会依照先后秩序存储起来,每组的地点偏移量也被称之为槽(slot),每一个槽相称于指针指向了区别组的末了一个记载。

  从图能够看到,页目次便是由众个槽构成的,槽相称于分组记载的索引。而后,由于记载是依照「主键值」从小到大排序的,以是咱们经由过程槽查找记载时,能够操纵二分法神速定位要盘查的记载正在哪一个槽(哪一个记载分组),定位到槽后,再遍历槽内的全数记载,找到对应的记载,无需从最小记载开首遍历通盘页中的记载链外。

  以下面那张图举个例子,5 个槽的编号判袂为 0,1,2,3,4,我思查找主键为 11 的用户记载:

   先二分得出槽旁边位是 (0+4)/2=2 ,2号槽里最大的记载为 8。由于 11 > 8,以是必要从 2 号槽后连续搜求记载; 再操纵二分搜求出 2 号和 4 槽的旁边位是 (2+4)/2= 3,3 号槽里最大的记载为 12。由于 11 < 12,以是主键为 11 的记载正在 3 号槽里; 再从 3 号槽指向的主键值为 9 记载开首向下搜求 2 次,定位到主键为 11 的记载,掏出该笔记录的讯息即为咱们思要查找的实质。

  看到第三步的期间,或许有的同窗会疑难,借使某个槽内的记载良众,而后由于记载都是单向链外串起来的,那如许正在槽外调找某个记载的时辰纷乱度未便是 O(n) 了吗?

  这点不必费心,InnoDB 对每一个分组中的记载条数都是有划定的,槽内的记载就惟有几条:

   第一个分组中的记载只可有 1 笔记录; 末了一个分组中的记载条数限度只可正在 1-8 条之间; 剩下的分组中记载条数限度只可正在 4-8 条之间。 B+ 树是奈何举办盘查的?

  下面咱们都是正在说一个数据页中的记载检索,由于一个数据页中的记载是无限的,且主键值是有序的,以是经由过程对全数记载举办分组,而后将组号(槽号)存储到页目次,使其起到索引效率,经由过程二分查找的技巧神速检索到记载正在哪一个分组,来低浸检索的时辰纷乱度。

  可是,当咱们必要存储大方的记载时,就必要众个数据页,这时咱们就必要思虑奈何树立适合的索引,能力便利定位记载所正在的页。

  为分析决这个题目,InnoDB 采取了 B+ 树行为索引。磁盘的 I/O 操纵次数对索引的操纵效力至合首要,因而正在构制索引的期间,咱们更目标于采取矮胖的 B+ 树数据组织,如许所必要举办的磁盘 I/O 次数更少,况且 B+ 树 更合适举办合节字的限度盘查。

  更详尽的为甚么采取 B+ 树行为索引的原由能够看我以前写的这篇:「索引为甚么能进步盘查功能?」

  InnoDB 里的 B+ 树中的每一个节点都是一个数据页,组织示希图如下:

  

  经由过程上图,咱们看出 B+ 树的特征:

   惟有叶子节点(最底层的节点)才寄存了数据,非叶子节点(其余下层节)仅用来寄存目次项行为索引。 非叶子节点分为区别宗旨,经由过程分层来低浸每一层的搜求量; 全数节点依照索引键巨细排序,形成一个双向链外,便于限度盘查;

  咱们再看看 B+ 树奈何告终神速查找主键为 6 的记载,以上图为例子:

   从根节点开首,经由过程二分法神速定位到适当页内限度蕴涵盘查值的页,由于盘查的主键值为 6,正在[1, 7)限度之间,以是到页 30 中查找更详尽的目次项; 正在非叶子节点(页30)中,连续经由过程二分法神速定位到适当页内限度蕴涵盘查值的页,主键值大于 5,以是就到叶子节点(页16)查找记载; 接着,正在叶子节点(页16)中,经由过程槽查找记载时,操纵二分法神速定位要盘查的记载正在哪一个槽(哪一个记载分组),定位到槽后,再遍历槽内的全数记载,找到主键为 6 的记载。

  能够看到,正在定位记载所正在哪一个页时,也是经由过程二分法神速定位到蕴涵该记载的页。定位到该页后,又会正在该页内举办二分法神速定位记载所正在的分组(槽号),末了正在分组内举办遍历查找。

   会集索引和二级索引

  别的,索引又能够分红会集索引和非会集索引(二级索引),它们差别就正在于叶子节点寄存的是甚么数据:

   会集索引的叶子节点寄存的是本质数据,全数完备的用户记载都寄存正在会集索引的叶子节点; 二级索引的叶子节点寄存的是主键值,而不是本质数据。

  由于外的数据都是寄存正在会集索引的叶子节点里,以是 InnoDB 存储引擎肯定会为外创修一个会集索引,且因为数据正在物理上只会存储一份,以是聚簇索引只可有一个。

  InnoDB 正在创修聚簇索引时,会按照区别的场景遴选区别的列行为索引:

   借使有主键,默许会操纵主键行为聚簇索引的索引键; 借使没有主键,就遴选第一个不蕴涵 NULL 值的独一列行为聚簇索引的索引键; 正在下面两个都没有的景况下,InnoDB 将自愿天生一个隐式自增 id 列行为聚簇索引的索引键;

  一张外只可有一个聚簇索引,那为了告终非主键字段的神速搜求,就引出了二级索引(非聚簇索引/辅助索引),它也是诈骗了 B+ 树的数据组织,可是二级索引的叶子节点寄存的是主键值,不是本质数据。

  二级索引的 B+ 树如下图,数据局限为主键值:

  

  因而,借使某个盘查语句操纵了二级索引,可是盘查的数据不是主键值,这时正在二级索引找到主键值后,必要去聚簇索引中获取数据行,这个经过就叫作「回外」,也便是说要查两个 B+ 树能力查到数据。只是,当盘查的数据是主键值时,由于只正在二级索引就能盘查到,不必再去聚簇索引查,这个经过就叫作「索引笼盖」,也便是只要要查一个 B+ 树就能找到数据。

   总结

  InnoDB 的数据是按「数据页」为单元来读写的,默许数据页巨细为 16 KB。每一个数据页之间经由过程双向链外的形势构制起来,物理上不相联,可是逻辑上相联。

  数据页内蕴涵用户记载,每一个记载之间用单项链外的方法构制起来,为了加快正在数据页内高效盘查记载,计划了一个页目次,页目次存储各个槽(分组),且主键值是有序的,因而能够经由过程二分查找法的方法举办检索从而进步效力。

  为了高效盘查记载所正在的数据页,InnoDB 采取 b+ 树行为索引,每一个节点都是一个数据页。

  借使叶子节点存储的是本质数据的便是聚簇索引,一个外只可有一个聚簇索引;借使叶子节点存储的不是本质数据,而是主键值则便是二级索引,一个外中能够有众个二级索引。

  正在操纵二级索引举办查找数据时,借使盘查的数据能正在二级索引找到,那末便是「索引笼盖」操纵,借使盘查的数据不正在二级索引里,就必要先正在二级索引找到主键值,必要去聚簇索引中获取数据行,这个经过就叫作「回外」。

  对于索引的实质再有良众,比方索引生效、索引优化等等,这些实质我下次正在讲啦!

文章推荐:

2022 年中国人工智能行业发展现状与市场规模分析 市场规模超 3000 亿元

该来的总要来! 切尔西老板将彻底退出英国市场

雷神黑武士四代开售:i7搭RTX3060不到9千元

智慧城市中 5G 和物联网的未来