精华内容
下载资源
问答
  • innodb索引原理
    2019-10-20 16:05:25

    1 简介       

           索引(Index)是帮助MySQL高效获取数据的数据结构。我们知道,数据库查询是数据库的最主要功能之一。但每种查找算法都只能应用于特定的数据结构之上,例如二分查找要求被检索数据有序,而二叉树查找只能应用于二叉查找树上,但是数据本身的组织结构不可能完全满足各种数据结构(例如,理论上不可能同时将两列都按顺序进行组织),所以,在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法。这种数据结构,就是索引。

           索引一般以文件形式存储在磁盘上,索引检索需要磁盘I/O操作。所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。在MySQL中,索引属于存储引擎级别的概念,不同存储引擎对索引的实现方式是不同的(例如树结构的选型和查找算法的实现),本文主要讨论InnoDB的索引实现方式。

          当数据保存在磁盘类存储介质上时,它是作为数据块存放。这些数据块是被当作一个整体来访问的,这样可以保证操作的原子性。硬盘数据块存储结构类似于链表,都包含数据部分,以及一个指向下一个节点(或数据块)的指针,不需要连续存储。所以-- 可以说数据库必须有索引,没有索引则检索过程变成了顺序查找,O(n)的时间复杂度几乎是不能忍受的。另一篇文章也会介绍mysql中如何建立索引。MYSQL索引建立(innoDB)需要注意,某些操作会使得数据库放弃索引而进行全表扫描。导致引擎放弃使用索引而进行全表扫描的条件。

         在 InnoDB 中,索引使用的数据结构是 B+ Tree

                                         

           这里的 B 是 Balance 的意思。B 类树的一个很鲜明的特点就是树的层数比较少,而每层的节点都非常多,树的每个叶子节点到根节点的距离都是相同的(这也是为什么叫 Balance Tree 的原因)。另外,树的每一个节点都是一个数据页,这样每个节点只需要一次 IO 就可以全部读取。这样的结构保证了查询数据时能尽量少地进行磁盘 IO,同时保证 IO 的稳定性。B+ Tree 和 B Tree 不同,B+ Tree 中,只能将数据存储在叶子结点中,内部节点将只包含指针,而 B Tree 可以将数据存储在内部的叶节点中。因此 B+ Tree 的关键优势是中间节点不包含数据,因此 B+ Tree 的大小远小于 B Tree,并且可以将更多数据存储到存储器中。另外,B+ Tree 的每一个叶子节点包含了到相邻的节点的链接,这样可以快速地进行范围遍历。

    为什么用B+ree 做索引

       1)  B+数是由B-数演变而来,所以B+数拥有B-数的所有特性
       2)  B+树的非叶子节点只保存关键字和子节点的地址,而叶子节点保留了当前路节点的所有节点的关键字、数据区和地址,所以要得到节点的数据就要到叶子节点上去获取,所以我们每次对数据的检索的时间都差不多,不像其他树,非叶子节点也有保留数据区,这样子当数据量庞大,当检索第一个跟最后一个的索引时间就相差比较大
       3)  B+树是一颗多路平衡查找树,由于它是多路的,所以它的高度比其他二叉树都矮,树的高度决定了检索数据的时间复杂度
    计算机默认检索的一页是4k,而mysql对这个4k做了调整增加到16k,这个一页是16k,假如这里保存的是一个id的索引树,那id设置为int类型,一个int类型为4个字节,那这一页可以保存的id的个数就可以这样算((16* 1024)/4),所以索引的类型和字节数都决定了数据库检索数据的效率,所以该id树的一个节点可以设置的路数就为((16*1024)/4)路,所以这一页就可以保存这么多数据,一次加载到内存中就可以加载那么多,充分利用了计算机的IO读取性能和空间局部性原理,极大降低了计算机IO的次数
       4)  B+树的叶子节点上保存一个指针,这个指针指向的是下一个叶子节点的指针,譬如第一路的叶子节点上数据有567这三个树,而第二路有8910,则第一路的7有个指针会指向第二路的8,这样做的好处是使数据自带有顺序性的特性,这个顺序性在我们做一个范围查询时,性能就得到充分的发挥,这个指针也是B-树跟B+树的区别之一

    MySQL 索引为什么要选用 B+ tree

      3 主索引和辅助索引
          在 InnoDB 存储引擎中,每一个索引都对应一棵 B+ Tree,InnoDB 的索引主要分为主索引和辅助索引:
          主索引:包含记录的文件按照某个 key 制定的顺序排序,这个 key 就是主索引,也就是主键,也被称为聚簇索引。因为无法同时把数据行存放在两个不同的地方,所以一个表只能有一个聚集索引。在 InnoDB 中,主索引的叶子节点存的是整行数据,这也意味着 InnoDB 中的表一定要有一个主索引;
          辅助索引:某个 key 指定的顺序与文件记录的物理顺序不同,这个 key 就是辅助索引。InnoDB 中的辅助索引在叶子节点中并不存储实际的数据,只会包含主索引的值 。这就意味着如果使用辅助索引进行数据的查找,只能查到主索引,然后根据这个主索引再次扫描以下主索引的树,进行一次回表操作;
          上面讲到,InnoDB 的表中要求必须有一个主键,那么可能有人会将身份证号这种唯一性的标识作为主索引,这样就大错特错了。刚刚说到主键也被称为聚簇索引,它是要按照顺序进行排序的,要求有聚簇性。如果将身份证号作为主键,不能保证每次插入的数据都是按照身份证号的顺序进行排列的,这就使得每次主键的插入都变得完全随机,可能导致每次插入一条数据都会引起页分裂的问题。
          所以在表结构定义的时候,应该使用一个具有聚集性的 key 作为主键,如果真的没有的话,可以使用一个 AUTO INCREMENT 代理键作为主索引,这样可以保证数据行是顺序写入的。如果你真的完全没有定义主键,InnoDB 会选择一个唯一的非空索引代替,但是如果没有这样的索引,InnoDB 会隐式定义一个主键来作为聚集索引。

     正因为 InnoDB 索引的这种结构,产生了一些限制:

    1 如果不是按照索引的最左列开始查找,则无法使用索引;
    2 不能跳过联合索引中的某些列;
    3 如果查询中有某个列的范围查询,则其右边所有列都无法使用索引优化查找;

    4 哈希索引

        InnoDB存储引擎使用哈希算法来查找字典,冲突机制采用链表,哈希函数采用除法散列。对于缓冲池的哈希表,在缓存池中的每页都有一个chain指针,指向相同哈希值的页。对于除法散列,m的值为略大于2倍缓冲池页数量的质数。如当前innodb_buffer_pool_size大小为10M,则共有640个16KB的页,需要分配1280个插槽,而略大于的质数为1399,因此会分配1399个槽的哈希表,用来哈希查询缓冲池中的页。 而对于将每个页转换为自然数,每个表空间都有一个space_id,用户要查询的是空间中某个连续的16KB的页,即偏移量(offset),InnoDB将space_id左移20位,再加上space_id和offset,即K=space_id<<20+space_id+offset,然后使用除法散列到各个槽中。

    自适应哈希索

           自适应哈希索引采用之前讨论的哈希表的方式实现。不同的是,这仅是数据库自身创建并使用的,DBA本身并不能对其进行干预。自适应哈希索引经哈希函数映射到一个哈希表中,因此对于字典类型的查找非常快速,如 SELECT* FROM TABLE WHERE index col=xxx。但是对于范围查找就无能为力了。通过命令 SHOW ENGINE INNODB STATUS可以看到当前自适应哈希索引的使用状况。

    5 全文索引

           通过前面章节的介绍,已经知道B+树索引的特点,可以通过索引字段的前缀( prefix)进行查找。例如,对于下面的查询B+树索引是支持的:SELECT FROM blog WHERE content like 'xXxs上述SOL语句可以查询博客内容以x开头的文章,并且只要 content添加了B+树索引,就能利用索引进行快速查询。然而实际这种查询不符合用户的要求,因为在更多的情况下,用户需要查询的是博客内容包含单词xxx的文章,即:SELECT FROM blog WHERE content like ' 8xxx8根据B+树索引的特性,上述SQL语句即便添加了B+树索引也是需要进行索引的扫描来得到结果。类似这样的需求在互联网应用中还有很多。例如,搜索引擎需要根据用户输入的关键字进行全文查找,电子商务网站需要根据用户的查询条件,在可能需要在商品的详细介绍中进行查找,这些都不是B+树索引所能很好地完成的工作。全文检索(Fu- Text Search)是将存储于数据库中的整本书或整篇文章中的任意内容信息查找出来的技术。它可以根据需要获得全文中有关章、节、段、句、词等信息,也可以进行各种统计和分析。在之前的 MySQL数据库中, InnoDB存储引擎并不支持全文检索技术,从InnoDB 1.2.x开始支持。

       MySQL · 引擎特性 · InnoDB 全文索引简介

       MySQL中InnoDB全文检索

     

      

    更多相关内容
  • MySQL Innodb 索引原理详解
  • InnoDB索引原理详解

    2020-10-13 09:49:33
     本篇介绍下Mysql的InnoDB索引相关知识,从各种树到索引原理到存储的细节。  InnoDB是Mysql的默认存储引擎(Mysql5.5.5之前是MyISAM,文档)。本着高效学习的目的,本篇以介绍InnoDB为主,少量涉及MyISAM作为对比。...

    摘要:

      本篇介绍下Mysql的InnoDB索引相关知识,从各种树到索引原理到存储的细节。

      InnoDB是Mysql的默认存储引擎(Mysql5.5.5之前是MyISAM,文档)。本着高效学习的目的,本篇以介绍InnoDB为主,少量涉及MyISAM作为对比。

      这篇文章是我在学习过程中总结完成的,内容主要来自书本和博客(参考文献会给出),过程中加入了一些自己的理解,描述不准确的地方烦请指出。

      1 各种树形结构

      本来不打算从二叉搜索树开始,因为网上已经有太多相关文章,但是考虑到清晰的图示对理解问题有很大帮助,也为了保证文章完整性,最后还是加上了这部分。

      先看看几种树形结构:

      1 搜索二叉树:每个节点有两个子节点,数据量的增大必然导致高度的快速增加,显然这个不适合作为大量数据存储的基础结构。

      2 B树:一棵m阶B树是一棵平衡的m路搜索树。最重要的性质是每个非根节点所包含的关键字个数 j 满足:┌m/2┐ - 1 <= j <= m - 1;一个节点的子节点数量会比关键字个数多1,这样关键字就变成了子节点的分割标志。一般会在图示中把关键字画到子节点中间,非常形象,也容易和后面的B+树区分。由于数据同时存在于叶子节点和非叶子结点中,无法简单完成按顺序遍历B树中的关键字,必须用中序遍历的方法。

      3 B+树:一棵m阶B树是一棵平衡的m路搜索树。最重要的性质是每个非根节点所包含的关键字个数 j 满足:┌m/2┐ - 1 <= j <= m;子树的个数最多可以与关键字一样多。非叶节点存储的是子树里最小的关键字。同时数据节点只存在于叶子节点中,且叶子节点间增加了横向的指针,这样顺序遍历所有数据将变得非常容易。

      4 B*树:一棵m阶B树是一棵平衡的m路搜索树。最重要的两个性质是1每个非根节点所包含的关键字个数 j 满足:┌m2/3┐ - 1 <= j <= m;2非叶节点间添加了横向指针。

     

      B/B+/B*三种树有相似的操作,比如检索/插入/删除节点。这里只重点关注插入节点的情况,且只分析他们在当前节点已满情况下的插入操作,因为这个动作稍微复杂且能充分体现几种树的差异。与之对比的是检索节点比较容易实现,而删除节点只要完成与插入相反的过程即可(在实际应用中删除并不是插入的完全逆操作,往往只删除数据而保留下空间为后续使用)。

      先看B树的分裂,下图的红色值即为每次新插入的节点。每当一个节点满后,就需要发生分裂(分裂是一个递归过程,参考下面7的插入导致了两层分裂),由于B树的非叶子节点同样保存了键值,所以已满节点分裂后的值将分布在三个地方:1原节点,2原节点的父节点,3原节点的新建兄弟节点(参考5,7的插入过程)。分裂有可能导致树的高度增加(参考3,7的插入过程),也可能不影响树的高度(参考5,6的插入过程)。

      B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟节点的指针。

      B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了)。如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针。可以看到B*树的分裂非常巧妙,因为B*树要保证分裂后的节点还要2/3满,如果采用B+树的方法,只是简单的将已满的节点一分为二,会导致每个节点只有1/2满,这不满足B*树的要求了。所以B*树采取的策略是在本节点满后,继续插入兄弟节点(这也是为什么B*树需要在非叶子节点加一个兄弟间的链表),直到把兄弟节点也塞满,然后拉上兄弟节点一起凑份子,自己和兄弟节点各出资1/3成立新节点,这样的结果是3个节点刚好是2/3满,达到B*树的要求,皆大欢喜。

      B+树适合作为数据库的基础结构,完全是因为计算机的内存-机械硬盘两层存储结构。内存可以完成快速的随机访问(随机访问即给出任意一个地址,要求返回这个地址存储的数据)但是容量较小。而硬盘的随机访问要经过机械动作(1磁头移动 2盘片转动),访问效率比内存低几个数量级,但是硬盘容量较大。典型的数据库容量大大超过可用内存大小,这就决定了在B+树中检索一条数据很可能要借助几次磁盘IO操作来完成。如下图所示:通常向下读取一个节点的动作可能会是一次磁盘IO操作,不过非叶节点通常会在初始阶段载入内存以加快访问速度。同时为提高在节点间横向遍历速度,真实数据库中可能会将图中蓝色的CPU计算/内存读取优化成二叉搜索树(InnoDB中的page directory机制)。

      真实数据库中的B+树应该是非常扁平的,可以通过向表中顺序插入足够数据的方式来验证InnoDB中的B+树到底有多扁平。我们通过如下图的CREATE语句建立一个只有简单字段的测试表,然后不断添加数据来填充这个表。通过下图的统计数据(来源见参考文献1)可以分析出几个直观的结论,这几个结论宏观的展现了数据库里B+树的尺度。

      1 每个叶子节点存储了468行数据,每个非叶子节点存储了大约1200个键值,这是一棵平衡的1200路搜索树!

      2 对于一个22.1G容量的表,也只需要高度为3的B+树就能存储了,这个容量大概能满足很多应用的需要了。如果把高度增大到4,则B+树的存储容量立刻增大到25.9T之巨!

      3 对于一个22.1G容量的表,B+树的高度是3,如果要把非叶节点全部加载到内存也只需要少于18.8M的内存(如何得出的这个结论?因为对于高度为2的树,1203个叶子节点也只需要18.8M空间,而22.1G从良表的高度是3,非叶节点1204个。同时我们假设叶子节点的尺寸是大于非叶节点的,因为叶子节点存储了行数据而非叶节点只有键和少量数据。),只使用如此少的内存就可以保证只需要一次磁盘IO操作就检索出所需的数据,效率是非常之高的。

      2 Mysql的存储引擎和索引

      可以说数据库必须有索引,没有索引则检索过程变成了顺序查找,O(n)的时间复杂度几乎是不能忍受的。我们非常容易想象出一个只有单关键字组成的表如何使用B+树进行索引,只要将关键字存储到树的节点即可。当数据库一条记录里包含多个字段时,一棵B+树就只能存储主键,如果检索的是非主键字段,则主键索引失去作用,又变成顺序查找了。这时应该在第二个要检索的列上建立第二套索引。  这个索引由独立的B+树来组织。有两种常见的方法可以解决多个B+树访问同一套表数据的问题,一种叫做聚簇索引(clustered index ),一种叫做非聚簇索引(secondary index)。这两个名字虽然都叫做索引,但这并不是一种单独的索引类型,而是一种数据存储方式。对于聚簇索引存储来说,行数据和主键B+树存储在一起,辅助键B+树只存储辅助键和主键,主键和非主键B+树几乎是两种类型的树。对于非聚簇索引存储来说,主键B+树在叶子节点存储指向真正数据行的指针,而非主键。

      InnoDB使用的是聚簇索引,将主键组织到一棵B+树中,而行数据就储存在叶子节点上,若使用"where id = 14"这样的条件查找主键,则按照B+树的检索算法即可查找到对应的叶节点,之后获得行数据。若对Name列进行条件搜索,则需要两个步骤:第一步在辅助索引B+树中检索Name,到达其叶子节点获取对应的主键。第二步使用主键在主索引B+树种再执行一次B+树检索操作,最终到达叶子节点即可获取整行数据。

      MyISM使用的是非聚簇索引,非聚簇索引的两棵B+树看上去没什么不同,节点的结构完全一致只是存储的内容不同而已,主键索引B+树的节点存储了主键,辅助键索引B+树存储了辅助键。表数据存储在独立的地方,这两颗B+树的叶子节点都使用一个地址指向真正的表数据,对于表数据来说,这两个键没有任何差别。由于索引树是独立的,通过辅助键检索无需访问主键的索引树。

      为了更形象说明这两种索引的区别,我们假想一个表如下图存储了4行数据。其中Id作为主索引,Name作为辅助索引。图示清晰的显示了聚簇索引和非聚簇索引的差异。

     

      我们重点关注聚簇索引,看上去聚簇索引的效率明显要低于非聚簇索引,因为每次使用辅助索引检索都要经过两次B+树查找,这不是多此一举吗?聚簇索引的优势在哪?

      1 由于行数据和叶子节点存储在一起,这样主键和行数据是一起被载入内存的,找到叶子节点就可以立刻将行数据返回了,如果按照主键Id来组织数据,获得数据更快。

      2 辅助索引使用主键作为"指针" 而不是使用地址值作为指针的好处是,减少了当出现行移动或者数据页分裂时辅助索引的维护工作,使用主键值当作指针会让辅助索引占用更多的空间,换来的好处是InnoDB在移动行时无须更新辅助索引中的这个"指针"。也就是说行的位置(实现中通过16K的Page来定位,后面会涉及)会随着数据库里数据的修改而发生变化(前面的B+树节点分裂以及Page的分裂),使用聚簇索引就可以保证不管这个主键B+树的节点如何变化,辅助索引树都不受影响。

      3 Page结构

      如果说前面的内容偏向于解释原理,那后面就开始涉及具体实现了。

      理解InnoDB的实现不得不提Page结构,Page是整个InnoDB存储的最基本构件,也是InnoDB磁盘管理的最小单位,与数据库相关的所有内容都存储在这种Page结构里。Page分为几种类型,常见的页类型有数据页(B-tree Node)Undo页(Undo Log Page)系统页(System Page) 事务数据页(Transaction System Page)等。单个Page的大小是16K(编译宏UNIV_PAGE_SIZE控制),每个Page使用一个32位的int值来唯一标识,这也正好对应InnoDB最大64TB的存储容量(16Kib * 2^32 = 64Tib)。一个Page的基本结构如下图所示:

      每个Page都有通用的头和尾,但是中部的内容根据Page的类型不同而发生变化。Page的头部里有我们关心的一些数据,下图把Page的头部详细信息显示出来:

     

      我们重点关注和数据组织结构相关的字段:Page的头部保存了两个指针,分别指向前一个Page和后一个Page,头部还有Page的类型信息和用来唯一标识Page的编号。根据这两个指针我们很容易想象出Page链接起来就是一个双向链表的结构。

      再看看Page的主体内容,我们主要关注行数据和索引的存储,他们都位于Page的User Records部分,User Records占据Page的大部分空间,User Records由一条一条的Record组成,每条记录代表索引树上的一个节点(非叶子节点和叶子节点)。在一个Page内部,单链表的头尾由固定内容的两条记录来表示,字符串形式的"Infimum"代表开头,"Supremum"代表结尾。这两个用来代表开头结尾的Record存储在System Records的段里,这个System Records和User Records是两个平行的段。InnoDB存在4种不同的Record,它们分别是1主键索引树非叶节点 2主键索引树叶子节点 3辅助键索引树非叶节点 4辅助键索引树叶子节点。这4种节点的Record格式有一些差异,但是它们都存储着Next指针指向下一个Record。后续我们会详细介绍这4种节点,现在只需要把Record当成一个存储了数据同时含有Next指针的单链表节点即可。

      User Record在Page内以单链表的形式存在,最初数据是按照插入的先后顺序排列的,但是随着新数据的插入和旧数据的删除,数据物理顺序会变得混乱,但他们依然保持着逻辑上的先后顺序。

      把User Record的组织形式和若干Page组合起来,就看到了稍微完整的形式。

      现在看下如何定位一个Record:

      1 通过根节点开始遍历一个索引的B+树,通过各层非叶子节点最终到达一个Page,这个Page里存放的都是叶子节点。

      2 在Page内从"Infimum"节点开始遍历单链表(这种遍历往往会被优化),如果找到该键则成功返回。如果记录到达了"supremum",说明当前Page里没有合适的键,这时要借助Page的Next Page指针,跳转到下一个Page继续从"Infimum"开始逐个查找。

      详细看下不同类型的Record里到底存储了什么数据,根据B+树节点的不同,User Record可以被分成四种格式,下图种按照颜色予以区分。

      1 主索引树非叶节点(绿色)

      1 子节点存储的主键里最小的值(Min Cluster Key on Child),这是B+树必须的,作用是在一个Page里定位到具体的记录的位置。

      2 最小的值所在的Page的编号(Child Page Number),作用是定位Record。

      2 主索引树叶子节点(黄色)

      1 主键(Cluster Key Fields),B+树必须的,也是数据行的一部分

      2 除去主键以外的所有列(Non-Key Fields),这是数据行的除去主键的其他所有列的集合。

      这里的1和2两部分加起来就是一个完整的数据行。

      3 辅助索引树非叶节点非(蓝色)

      1 子节点里存储的辅助键值里的最小的值(Min Secondary-Key on Child),这是B+树必须的,作用是在一个Page里定位到具体的记录的位置。

      2 主键值(Cluster Key Fields),非叶子节点为什么要存储主键呢?因为辅助索引是可以不唯一的,但是B+树要求键的值必须唯一,所以这里把辅助键的值和主键的值合并起来作为在B+树中的真正键值,保证了唯一性。但是这也导致在辅助索引B+树中非叶节点反而比叶子节点多了4个字节。(即下图中蓝色节点反而比红色多了4字节)

      3 最小的值所在的Page的编号(Child Page Number),作用是定位Record。

      4 辅助索引树叶子节点(红色)

      1 辅助索引键值(Secondary Key Fields),这是B+树必须的。

      2 主键值(Cluster Key Fields),用来在主索引树里再做一次B+树检索来找到整条记录。

      下面是本篇最重要的部分了,结合B+树的结构和前面介绍的4种Record的内容,我们终于可以画出一幅全景图。由于辅助索引的B+树与主键索引有相似的结构,这里只画出了主键索引树的结构图,只包含了"主键非叶节点"和"主键叶子节点"两种节点,也就是上图的的绿色和黄色的部分。

      把上图还原成下面这个更简洁的树形示意图,这就是B+树的一部分。注意Page和B+树节点之间并没有一一对应的关系,Page只是作为一个Record的保存容器,它存在的目的是便于对磁盘空间进行批量管理,上图中的编号为47的Page在树形结构上就被拆分成了两个独立节点。

      至此本篇就算结束了,本篇只是对InnoDB索引相关的数据结构和实现进行了一些梳理总结,并未涉及到Mysql的实战经验。这主要是基于几点原因:

      1 原理是基石,只有充分了解InnoDB索引的工作方式,我们才有能力高效的使用好它。

      2 原理性知识特别适合使用图示,我个人非常喜欢这种表达方式。

      3 关于InnoDB优化,在《高性能Mysql》里有更加全面的介绍,对优化Mysql感兴趣的同学完全可以自己获取相关知识,我自己的积累还未达到能分享这些内容的地步。

      另:对InnoDB实现有更多兴趣的同学可以看看Jeremy Cole的博客(参考文献三篇文章的来源),这位老兄曾先后在Mysql,Yahoo,Twitter,Google从事数据库相关工作,他的文章非常棒!

    参考文献:

     

    [1] Jeremy Cole The physical structure of InnoDB index pages

     

    [2] Jeremy Cole B+Tree index structures in InnoDB

     

    [3] Jeremy Cole The physical structure of records in InnoDB

     

    [4] 姜承尧  MySQL技术内幕-InnoDB存储引擎 第二版

     

    [5] Schwartz,B / Zaitsev,P / Tkach 高性能Mysql 第三版

    展开全文
  • 回想四年前,我在学习mysql的索引这块的时候,老师在讲索引的时候,是像下面这么说的 索引就像一本书的目录。而当用户通过索引查找数据时,就好比用户通过目录查询某章节的某个知识点。这样就帮助用户有效地提高了...
  • 本文主要从整体上把INNODB索引涉及到的知识点进行梳理,让读者从整体把握索引原理,具体内容还需要读者自行查看MySQL技术内幕一书,因为网上大多数文章基本都是拷贝这本书的内容,并且有些文章会误导读者,具体...

    本文主要从整体上把INNODB的索引涉及到的知识点进行梳理,让读者从整体把握索引的原理,具体内容还需要读者自行查看MySQL技术内幕一书,因为网上大多数文章基本都是拷贝这本书的内容,并且有些文章会误导读者,具体的内容还是耐心点看书吧!

    1.索引是什么?

    索引就像是一本书的目录,假设我们想要在书中找到某一小节的内容,如果没有目录,我们是不是要从头到尾顺序找一遍,这非常浪费时间,但有了目录,我们就可以快速定位到该小节的页码,并找到该小结的内容。索引的作用就是这样,可以帮助我们快速找到指定的内容。

    2.MySQL  InnoDB索引的存储结构

    InnoDB使用的是B+tree数据结构,所有的记录都在叶子节点上,并且是按照顺序存放的,根节点和分支节点中不保存数据,只用于索引。具体可以看这篇文章:B+tree数据结构

    3.MySql的系统架构图


    从图中可以看出,mysql底层是使用文件系统来存储数据库。对于文件系统,大家需要区了解一下扇区、磁盘块等相关内容,这部分是mysql索引物理实现的基础。

    4.InnoDB的逻辑存储结构

    从InnoDB存储引擎的逻辑存储结构看,所有的数据都被逻辑地存放在一个空间中,称之为表空间。表空间又由段(segment)、区(extent)、页(page)组成。逻辑存储结构如下图所示:

     表空间:在默认情况下InnoDB引擎有一个共享表孔甲ibdata1,即所有的数据都存放在这个表空间中,如果用户启用了参数innodb_file_per_table,则每张表内的数据可以单独存放到一个表空间内。此时,你会发现每一个表都有一个 表名.frm文件和 表名.ibd文件。注意:这些单独的表空间文件只存储该表的数据、索引和插入缓冲BITMAP等信息。其余信息还是存放在默认的表空间。

    :区是由连续页组成的空间,每个区的大小位1MB.为了保证区中页的连续性,InnoDB存储引擎一次从磁盘申请4-5个区。默认情况下,存储引擎页的大小为16KB,即一个区中一共有64个连续的页。

    :页是InnoDB磁盘管理的最小单位,默认大小是16KB.常见的页类型有:数据页 undo页 系统页 插入缓冲位图页等。页的数据结构如下图所示:

    记录行:InnoDB存储引擎是面向行的,也就是说数据是按行存入.ibd文件的,而行是有格式的,就像TCP协议一样,每一个二进制都代表了各自的含义,无规矩不成方圆。InnoDB行格式有四种,Compact、Redundant、Compressed和Dynamic。只要了解一种就可以了,大同小异,大体意思就是我这一行的长度是多少,下一条记录的位置在哪里等。数据结构如下图所示:

    以上数据结构都是从逻辑层面进行的抽象,那么物理结构是怎样的呢?

    我们现在在本地数据库添加一个student表,并向其中添加两条记录。如下图所示:

    我们使用 UltraEdit软件打开School.ibd文件,如下图所示:

     数据页是从0x0000c0000(16K*3=0xc000)处开始,这也就验证之前说的页的大小是16KB,保证了同一页的数据在连续的磁盘块上,提高了查询效率。具体的二进制文件分析请看MySQL技术内幕。

    5.InnoDB和MyISAM索引的区别

    MYISAM是按列值与行号来组织索引的。它的叶子节点中保存的实际上是指向存放数据的物理块的指针。MYISAM使用的是非聚簇索引,非聚簇索引的两颗B+树看上去没有任何不同,节点的结构完全一致只是存储的内容不一样。主键索引的B+树存储的是主键,而辅助索引B+树存储的是辅助键。表数据存储在独立的地方,这两颗B+树的叶子节点保存了数据存储的真实物理地址。

    InnoDB 只聚集在同一个页面中的记录。通常向下读取一个节点的动作可能会是一次磁盘IO操作,不过非叶节点通常会在初始阶段载入内存以加快访问速度。聚集索引保存的是数据的复制,所以控制的是逻辑顺序,即使物理地址发生改变,行号变化,都不会影响聚集索引。InnoDB主键索引的叶节点存储的是主键值和剩余的列值,也就是存储了真实的记录,而辅助键索引存储的是索引值和主键值,这样设计的好处是,当记录由于行移动或者数据页分裂合并等操作造成记录的位置发生改变时,只需要更新主键索引,其他的辅助键索引完全不用变。而MyISAM叶节点存储的都是真实物理地址,所以当记录的地址发生改变时,所有的索引都需要更新。

    如下图所示:

    6. 使用自增ID做主键的理由

    聚簇索引的物理存放顺序和主键索引的顺序是相同的,只要索引是相邻的,那么对应的数据也一定相邻的存放在磁盘上。而如果主键不是自增ID,可以想象,聚簇索引需要不断的进行分页,调整记录的物理地址,这样是非常耗费时间的。使用自增主键可以让索引结构变得紧凑,磁盘碎片少,效率高。

    7.聚簇索引的列的选择

    • 主键列,该列在where子句中使用并且插入是随机的。
    • 按范围存取的列,如pri_order > 100 and pri_order < 200。
    • 在group by或order by中使用的列。
    • 不经常修改的列。
    • 在连接操作中使用的列。

    总结InnoDB索引巧妙的利用文件系统中磁盘块的概念,使用页来进行作为B+tree树的节点,这样可以在从磁盘读取每一个页的时候,保证同一页的数据相邻存放,提高了读取的效率。

    思考题:我们知道聚簇索引适合范围存取,假设我们对列  A添加辅助索引 ,然后以A列作为查询条件:

    select * from student where A>10 and A<100 这个查询是怎么使用索引的?如何提高查询效率?

    答案:Multi_Range Read优化  随机访问转化为顺序访问。

    参考文献

    MySQL技术内幕:InnoDB存储引擎

    1.MySQL索引背后的数据结构及算法原理

    2.浅谈算法和数据结构: 十 平衡查找树之B树

    3.聚簇索引与非聚簇索引

    展开全文
  • Mysql InnoDB索引原理

    2018-09-02 21:11:51
    本文的目的希望让读者能够掌握索引的基本概念,做到知其然也知其所以然,接下来笔者将从以下两个角度为你阐述Mysql索引。 何为索引 使用索引的正确姿势 Mysql索引是什么 A data structure that provides a ...

    Mysql InnoDB索引原理

    9b90a7872fcd962d04017237dbabc5aa

    索引这个概念说出来好像大家都知道,但是又有多少人能说出个所以然来呢?
    本文的目的希望让读者能够掌握索引的基本概念,做到知其然也知其所以然,接下来笔者将从以下两个角度为你阐述Mysql索引

    何为索引
    使用索引的正确姿势

    Mysql索引是什么

    A data structure that provides a fast lookup capability for rows of a table, typically by forming a tree structure (B-tree) representing all the values of a particular column or set of columns.
    —引用自mysql官方文档

    简单来说索引是一种数据结构(通常是树结构B-tree),这个数据结构中存放着特定的列或列集,以提供快速的查找功能。
    举一个例子来帮助大家理解,图书的目录,目录即索引,读者根据你想要查看的内容(索引),从目录中找到对应的页码(数据指针),定位到最终内容。

    索引类型

    Mysql的索引由储存引擎实现,不同的储存引擎支持的索引可能会不一样,本文只讲解最常见的索引类型B-Tree索引(这里的B是Balance的缩写)。

    B+Tree

    图1-1 建立在B-Tree结构(从技术上来说是B+Tree)上的索引

    B-Tree由根节点(图中未画出)、普通节点和叶子节点构成,普通节点存放指向下一节点的指针,具体指向数据的指针则存放在叶子结点中(所有叶子结点都在最后一层)。

    B-Tree索引之所以能够加快数据的访问速度,是因为在查找数据时不需要去一行行的查找并比较数据(全表扫描),而是从树的根节点开始比较查找,根据要查找的值一级一级的去比较节点页的值拿到下级指针(定义了子节点中值的上限和下限),最终找到索引所在的叶子页并拿到数据指针。

    聚簇索引

    实际上不是一种索引类型,其本质就是B-Tree索引,区别在于其叶子节点的存放的数据,叶子节点将不会存放指向数据的指针,而是直接存放数据行即每个叶子节点就是一行数据,即聚簇索引是InnoDB真正储存数据的地方。

    InnoDB通过主键来聚集数据,默认聚簇索引索引的列为主键,如果没有定义主键,InnoDB会选择一个默认的非空索引代替,如果没有这样的索引,InnoDB会隐式的定义一个主键作为聚簇索引。

    二级索引

    可以理解为普通的B-Tree索引,非聚簇索引,这里唯一要明确的一点是二级索引叶子节点中储存的“行指针”其本质是主键,即聚簇索引中的键。所以当使用二级索引查询时需要进行二次查询,先从二级索引获取主键,再使用主键从聚簇索引中获取数据行(这里排除覆盖索引的情况)。

    简单的例子

    看了上面的聚簇索引和二级索引,相信很多读者还是存在一定的认知模糊,下面通过一个《高性能Mysql》中关于InnoDB数据分布的例子来帮助大家,更好的认识聚簇索引和二级索引究竟如何工作。

    下面是这个例子的表结构,layout_test表中有两个int类型字段,其中col1列作为主键,同时为col2列生成普通索引。

    CREATE TABLE layout_test (
    	col1 int NOT NULL,
    	col2 int NOT NULL,
    	PRIMARY KEY(col1),
    	KEY(col2)
    );
    

    layout_test表的聚簇索引部分

    2b700d4ca4b4b6c62d65a1798bdee670

    图1-2 表layout_test的聚簇索引

    简单讲解一下上图:

    1.首先大家可以先忽略其中的事务ID和回滚指针,因为这和理解索引部分暂时没有关系,有兴趣的读者可以另行了解。

    2.上图只是包含了聚簇索引的叶子节点部分,可以看到叶子节点中并没有储存数据指针,而是储存了主键col1和剩下的列col2,即每一个叶子节点我们可以理解成一条数据记录。比如第一个节点:主键列col1值为3、剩余列col2值为93其包含了这条记录的所有数据。

    3.这里我想吐槽一下这个例子,其实蛮容易让人误解的,如果再新增一个col3列的话,其实能更方便的将聚簇索引和二级索引区分开来,这里我们假设有col3,那么上图的每个叶子节点都将多一个col3列的值。

    **layout_test表的二级索引col2**

    5e498ea3b5eef0596f54f66460a050d5

    图1-3 表layout_test的col2列索引

    1.图1-3很简单也很好理解,这里简单说明一下,二级索引中每个叶子节点存放了两种数据,分别是索引键即col2,和主键col1。上图最后一个叶子节点:93是col2的值,3则是主键col1。

    2.这里还是跟上面一样,如果表layout_test还有个col3列,上图不会有任何的变化,二级索引每个叶子节点只会存储索引键和主键。

    借助上面的例子,用两个分别以col1和col2字段作为查询条件的SQL,为大家演示InnoDB的聚簇索引是如何工作的。

    #以col1作为查询条件
    SELECT col1, col2, col3 FROM layout_test WHERE col1 = 3;
    
    #以col2作为查询条件
    SELECT col1, col2, col3 FROM layout_test WHERE col2 = 93;
    

    为了防止“覆盖索引”让大家引起歧义,这里假设还有一个col3字段

    **第一条SQL执行:**根据主键col1 = 3,查询引擎会直接在聚簇索引中找到键为3的叶子节点。即图1-2的第一个叶子节点,其中包含了键col1,和剩余的字段col2和col3。

    **第二条SQL执行:**根据主键col2 = 93,查询引擎会从二级索引中查找键为93的叶子节点。即图1-3中的最后一个叶子节点,从中拿到主键3,然后再根据主键从聚簇索引中查找。即二次查询。(这里解释一下为什么需要假设一个字段col3,因为如果只有两个字段的话,其实只要查一次二级索引就可以拿到所有数据了,二级索引中已经包含了键col2和主键col1,这就是覆盖索引可以加速查询的道理,因为不需要再去查一遍聚簇索引,性能自然高)


    写在最后

    索引这个概念,细讲可能花一本书版本都讲不完,如何正确使用索引就留在下一篇跟大家分享。这里只是很粗浅的跟大家介绍了关于InnoDB索引的概念,目的是让不熟悉索引这块知识的读者,对其有个大体的概念。对于有兴趣深入了解的读者,强烈推荐《高性能Mysql》这本书,本文的大多数观点也是来源于此。
    碍于笔者所学有限,本文如有表述不当处欢迎于留言中指出。

    参考材料
    1.《高性能Mysql》
    2. [mysql开发手册](https://dev.mysql.com/doc/

    展开全文
  • B+树由 B 树和索引顺序访问方法演化而来,但是在现实使用过程中几乎已经没有使用 B 树的情况了。 B+树的定义在很多数据结构书中都能找到,非常复杂,我们概略它的定义,B+树是 B 树的一种变形形式,B+树上的叶子结点...
  • MySQL的索引可以大大提高MySQL的检索速度,在大厂的面试中也多会问关于索引和事务相关的问题,本篇我们来详细介绍MySQL中的索引及其使用和优化。
  • https://www.cnblogs.com/shijingxiang/articles/4743324.html
  • INNODB索引实现原理

    2019-12-30 19:27:03
    本篇继续整理Innodb索引实现原理。 二 B+树 B+树属于索引的基础,不在详细介绍插入删除过程。只介绍特点。 1 搜索二叉树:每个节点有两个子节点,数据量的增大必然导致高度的快速增加,显然这个不适合作为大量数据...
  • MySQL InnoDB 索引原理

    2021-01-22 18:15:12
    MySQL InnoDB 索引原理
  • InnoDB索引文件:3. 索引类型: 3.1. 主键索引(Primary Key): 3.2. 二级索引(辅助索引):4. 索引数据结构: 4.1. MyISAM索引实现: 4.2. InnoDB 索引实现: 1. 存储引擎:  存储引擎是不同数据文件在磁盘...
  • SELECT * FROM table WHERE a = 1 and b = 2 and c = 3;
  • MyISAM与InnoDB索引原理剖析

    千次阅读 2018-06-05 16:13:41
     在MySQL中,索引属于存储引擎级别的概念,不同存储引擎对索引的实现方式是不同的,本文主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式。 MyISAM索引实现  MyISAM引擎使用B+Tree作为索引结构,叶节点的data....
  • 转载:https://www.cnblogs.com/shijingxiang/articles/4743324.html
  • innoDB 索引结构详解

    2020-12-14 18:41:54
    1、数据库索引 innoDB和MyISAM对比 区别 innoDB MyISAM 事物支持 支持 不支持 锁粒度 行锁 表锁 并发性 高并发 低并发 构成结构和缓存机制 数据和索引文件都存在在.Idb文件里,并且都缓存在内存里。 ...
  • 1、索引数据结构2、InnoDB索引的设计(1)计算机原理(2)查找过程(3)聚族索引与二级索引(4)创建索引及索引的类型(5)索引的缺点(6)外键及作用 1、索引数据结构 哈希索引(Hash indexes)采用哈希表来对键值...
  • MySQL的InnoDB索引原理详解(讲的很好)

    千次阅读 2016-09-04 17:15:11
    本篇介绍下Mysql的InnoDB索引相关知识,从各种树到索引原理到存储的细节。 InnoDB是Mysql的默认存储引擎(Mysql5.5.5之前是MyISAM,文档)。本着高效学习的目的,本篇以介绍InnoDB为主,少量涉及MyISAM作为对比。 ...
  • 摘要本文介绍MySQL的InnoDB索引相对底层原理相关知识,涉及到B+Tree索引和Hash索引,但本文主要介绍B+Tree索引,其中包括聚簇索引和非聚簇索引,InnoDB数据页结构详解,B+Tree索引的使用以及优化,同时还有B+Tree...
  • B+Tree实现原理和基本知识 B+Tree实现原理 MyISAM 索引(叶子节点存放指向记录地址) MyISAM 引擎使用 B+Tree 作为索引结构,叶节点的 data 域存放的是数据记录的地址 上图中,我们以Col1为主键primary Key。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 56,192
精华内容 22,476
关键字:

innodb索引原理