精华内容
下载资源
问答
  • 浅析innoDB索引结构

    2020-01-08 15:44:44
    浅析innoDB索引结构 No.1 引言 在上两期分享了innoDB锁机制,innoDB存储结构,相信大家对innoDB也有了一定的了解, 今天将在上期存储结构的基础上,详细聊聊我们平时使用较多的innoDB索引是怎么回事? No.2 ...

    浅析innoDB索引结构

    No.1

    引言

     

    在上两期分享了 innoDB锁机制,innoDB存储结构,相信大家对innoDB也有了一定的了解, 今天将在上期存储结构的基础上,详细聊聊我们平时使用较多的innoDB索引是怎么回事?

    No.2

    课前提问

     

    1. 为什么InnoDB表必须有主键,并且推荐使用整型的自增主键?没有主键怎么办?

    2.  为什么非主键索引结构叶子节点存储的是主键值?

    3. 不考虑其他因素,主键长度8B+指针6B,一行数据1k,Innodb引擎三层的索引结构能存多少数据?

    No.3

    磁盘读取

     

     

    为什么要讲这一章

     

    为啥子要讲磁盘读取呢,我们不是要讲索引结构吗? 这有因必有果,如果说索引是果的话,那磁盘读取就是因。相信阅读过上篇innoDB存储结构的同学都知道,对于innoDB来讲,不管是索引还是数据本身都是以文件的形式存储在磁盘上的,那么对于mysql数据的操作本质上就是磁盘I\O,换而言之,磁盘I\O的速度决定了数据库的操作速度,所以下面我们就来先研究研究磁盘I\O是咋回事。

     

    磁盘构造

     

    先来介绍几个基本概念

    • 磁头:由图所示,磁头就是与盘片磁道直接接触的东西,通过盘片上的凹凸(0,1)进行数据读取。

    • 磁道:可以理解为盘片就是由一圈圈磁道组成的,最外侧定义为0磁道,依次向内。

    • 扇区:可以理解为我们用分蛋糕的形式将盘片分割,每一块就是一个扇区。

    • 柱面:由图可知一个磁盘是由多个磁头和盘片组成的,主轴旋转也是多磁头同步的,所以我们把多盘片的同磁道组成的圆柱面叫做柱面,读写数据也是按柱面操作的,写满一个柱面才会写下一个柱面。

     

    磁盘读写流程

     

    磁盘对数据的读取我们可以大致分为3步

    1. 寻道:找到数据所在的磁道(柱面)(此步最耗时,物理结构改变)

    2. 旋转:找到对应扇区

    3. 数据传输:和主存交互数据

    磁盘I\O时间 = 寻道时间+旋转时间+数据传输时间

     

    顺序读取和随机读取

     

    由上述流程可知,对读取时间影响最大的就是寻道这个步骤,显然若要用到的数据都在一个磁道扇面的话,那么仅需一次寻道就可加载完成,若目标数据分布在盘片的各个磁道上,则需要多次寻道,时间自然更长。

     

    局部性原理

     

    当一个数据被用到时,其附近的数据也通常会马上被使用。

     

    预读机制

     

    预读:页是计算机管理存储器的逻辑块,硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储块称为一页(在许多操作系统中,页的大小通常为4k)

    主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时,会触发一个缺页异常,此时系统会向磁盘发出读盘信号,磁盘会找到数据所在当前页并向后连续读取一页或几页载入内存中,这个操作就叫做预读。

    根据上述的局部性原理,操作系统对于磁盘I\O做了预读来进行优化,这使得顺序读取的磁盘IO次数进一步减少,从而加快加载速度。

    No.4

    innoDB的B+树索引

     

     

    什么是索引

     

    MySQL官方对索引的定义为: 索引(Index)是帮助MySQL高效获取数据的数据结构。

    索引的本质:索引是数据结构,而且是实现了高级查找算法的数据结构

    通俗的理解:索引就好比一本书的目录,可以让你直接找到目标的页数。

     

    为啥要用索引

     

    当有了索引后,我们搜索数据的流程变为:

    • 磁盘读取索引信息

    • 根据索引信息确定目标记录位置

    • 再次进行磁盘IO则可读取到目标数据

    相对于无索引遍历数据的方式大大减少IO次数,增加读写性能。一般使用磁盘I/O次数评价索引结构的优劣。

     

    B+树数据结构

     

    m阶的B+树定义如下:

    1. 根节点至少有两个孩子

    2. 每个中间节点都包含k个元素和k个孩子,

      其中 m/2 <= k <= m 

    3. 每一个叶子节点都包含k-1个元素,

      其中 m/2 <= k <= m

    4. 非叶节点不存储数据,只存索引

    5. 所有数据存在叶子节点,有序单链表

    本文因重点不在于对数据结构的讲解,所以为什么innoDB选用B+树而不是选用二叉平衡树,链表等等其他数据结构做索引,B+相对于B树的优点等问题,请自行学习,或等待以后的分享中讲解。

    innoDB的B+树

    1.  叶子节点为实际数据,并且为双向链表

    2. 每个节点等同于innoDB存储结构中的一个页,这也保证了每个节点的数据,物理和逻辑上都在同一个页中,一个节点的载入就是一个页的载入。

    3.  对于innoDB的B+树来说,树的阶=(一个页 / 索引字段长度),这也可以解释为什么不推荐索引字段过长,因为索引字段过长会导致阶变小,从而导致树的高度变高,最终导致索引文件过大。

    由此我就可以得出课前提问的第3问的答案,具体流程在文章结尾统一给出。

     

    innoDB基于B+树的聚集索引

     

    1. 对于innoDB来说 , 数据文件本质上就是B+树实现的聚集索引文件,叶子节点存储了具体的行数据,这也就解释了开篇的问题,innoDB是必须要有主键的,若没有设置innoDB也会默认生成主键,但此主键不可见.

    2. 因为磁盘由预读机制,并且innoDB数据页内物理地址是连续的(页和页之间是逻辑连续),所以推荐使用整形的自增主键,这样能保证数据文件的存储是顺序存储,保证了数据按序填满数据页。

     

    innoDB基于B+树的非聚集索引

     

    对于非主键建立的非聚集索引来说,区别在于叶子节点存储的不在是数据,而是主键值。

    No.5

    数据页结构(节点)

     

    No.6

    根据索引查找数据

     

    innoDB通过索引结构查找数据的流程为:

    以上图为例寻找id=11的行数据。

    1. 磁盘io加载索引段,11<21根据索引确定在p1页

    2. 磁盘io加载p1页,11=11确定数据在p11页

    3. 磁盘io加载p11页数据至主存,通过页内的稀疏索引进行二分查找到目标数据行

    No.7

    习题答案

     

     

     

     

    问题一:为什么InnoDB表必须有主键,并且推荐使用整型的自增主键?没有主键怎么办?

     

     

     

    1. 必须有主键,因为数据文件本质是聚集索引文件

    2. 若未指定innoDB或默认指定隐式主键

    3. 整形自增主键,使得innoDB的数据文件在物理结构上数据连续,搭配磁盘IO的预读,性能更好,并且在检索时比对索引值效率高,减少树的高度和分裂次数

     

     

     

    问题二:为什么非主键索引结构叶子节点存储的是主键值?                                  

     

    1. 节省空间,行数据只存储一份,在主键形成的聚集索引文件中。

    2. 提高主键复用,保证主键索引一致性

    问题三:不考虑其他因素,主键长度8B+指针6B,一行数据1k,Innodb引擎三层的索引结构能存多少数据?

    第一层根节点内的元素数= (16KB/14B)= 1170个

    第二层节点数 = 第一层根节点内的元素数 = 1170个

    叶子节点数量 = 1170*1170 = 1,368,900个

    每个叶子大小 = 页的大小 = 16KB

    每个叶子内行数 = 16KB/1KB = 16条

    数据行数 =  叶子节点数量*每个叶子内行数

                    =  1,368,900*16 

                    =  21,902,400条

     

    END

    希望大家踊跃留言讨论

    展开全文
  • 浅析InnoDB索引结构

    2020-12-15 00:57:41
    InnoDB表的索引有哪些特性,以及索引组织结构是怎样的 1、InnoDB聚集索引特点 我们知道,InnoDB引擎的聚集索引组织表,必然会有一个聚集索引。 行数据(row data)存储在聚集索引的叶子节点(除了发生overflow的列,...
  • innoDB 索引结构详解

    2020-12-14 18:41:54
    1、数据库索引 innoDB和MyISAM对比 区别 innoDB MyISAM ...构成结构和缓存机制 数据和索引文件都存在在.Idb文件里,并且都缓存在内存里。...索引文件都扩展名.MYI(MYIndex...2-1、InnoDB的体系结构有:内存结构,线程,
  • 2. InnoDB索引结构与读取方式总结 InnoDB索引结构与读取方式总结可总结如下: InnoDB的索引使用B+树结构,非叶子节点保存指向非叶子节点或叶子节点的指针,在叶子节点保存真正的数据,叶子节点在最低的同一层级,...

    1. 前言

    以下对InnoDB索引的结构与读取方式进行了整理,分析MySQL索引使SQL语句执行加速的原理,针对使用InnoDB 5.6版本的MySQL。

    2. InnoDB索引结构与读取方式总结

    InnoDB索引结构与读取方式总结可总结如下:

    • InnoDB的索引使用B+树结构,非叶子节点保存指向非叶子节点或叶子节点的指针,在叶子节点保存真正的数据,叶子节点在最低的同一层级,相互之间形成了双向链表。

    • B+树中的记录是有序的,在B+树中查找一条记录的时间复杂度为O(logbn),b为B+树的内部节点的最大子节点数量。

    • InnoDB在磁盘和内存之间一次传输多少数据的单位为页,页大小默认为16KB。

    • InnoDB的索引分为聚簇索引与二级索引,聚簇索引中包含了整行的数据,二级索引包含二级索引对应的列及聚簇索引的键。

    • 在MySQL 8.0之前的版本,索引记录以升序存储;在MySQL 8.0之后的版本中,索引记录支持以升序或降序存储。

    • InnoDB的索引B+树的叶子节点保存的数据格式为页,页的文件页头中包含了指向上一页与下一页的指针,即页之间构成了双向链表结构。

    • 一页至少包含两条记录,记录的额外字节(记录头)中包含指向页中下一条记录的指针,即一页中的记录构成了单向链表。

    • 页中的页目录使得对页中的记录进行搜索时,可以进行二分查找。

    • 索引键前缀的长度默认值为767个字节,索引键前缀的长度及记录中可变长度列存储位置由行格式及innodb_large_prefix变量决定。

    • 页分裂与页合并发生的时机与MERGE_THRESHOLD参数值有关,频繁发生时可能对性能产生影响。

    • Buffer Pool与Change Buffer分别对索引的读/写操作进行缓存,可以减少I/O次数,提高效率。

    3. 索引的实现位置与作用

    参考《High Performance MySQL, 3rd Edition》。

    索引在存储引擎层实现,不是在MySQL Server层实现。

    索引的作用如下:

    • 索引可以减少MySQL服务器需要检查的数据量;

    • 索引帮助MySQL服务器避免排序及使用临时表;

    • 索引将随机I/O转换为顺序I/O。

    4. InnoDb索引结构

    4.1. InnoDb索引使用B+树还是B树

    在MySQL 5.6参考手册中,关于索引结构的表述均使用“B-tree”。参考MySQL内部手册 https://dev.mysql.com/doc/internals/en/innodb-fil-header.html ,InnoDB索引使用的结构为B+树。

    4.2. MySQL如何使用索引

    参考 https://dev.mysql.com/doc/refman/5.6/en/mysql-indexes.html 。

    索引用于快速查找具有特定列值的行。如果没有索引,MySQL必须从第一行开始,通读整个表以找到相关的行。表越大,花费越多。如果表中有相关列的索引,MySQL可以快速确定要在数据文件中间查找的位置,而不必查看所有数据。这比顺序读取每一行要快得多。

    大多数MySQL索引(PRIMARY KEY,UNIQUE,INDEX和FULLTEXT)存储在B+树中。

    4.3. B+树

    参考 https://en.m.wikipedia.org/wiki/B%2B_tree 、 https://en.wikibooks.org/wiki/Algorithm_Implementation/Trees/B%2B_tree 、 https://en.m.wikipedia.org/wiki/B-tree。

    B+树是平衡的N叉树,每个节点的子节点数量是可变的,通常数量很大。B+树由根节点、内部节点和叶子节点组成。根节点可以是叶子节点,也可以具有两个或更多叶子节点。

    B+树是B树的变体。在B+树中,所有数据都保存在叶子节点中。内部节点仅包含key和树指针。所有叶子处于相同的最低水平。叶子节点也作为链表链接在一起,便于范围查询。

    B+树中的数据是有序的。B+树的主要价值在于存储数据,以便在面向块的存储环境(尤其是文件系统)中进行有效的检索。B+树具有很高的扇出度(指向节点中子节点的指针数量,通常为100或更多),这减少了在树中找到一个元素所需的I/O操作数量。

    B+树的内部节点的最大子节点数量,称为order或分支因子(branching factor, b)。

    对于order为b的B+树,插入一条记录的时间复杂度为O(logbn)。

    查询一条记录的时间复杂度为O(logbn)。

    使用范围内出现的k个元素执行范围查询时间复杂度为O(logbn + k)。

    B+树的示例如下所示:

    4.4. 聚簇索引(Clustered Index)与二级索引(Secondary Index)

    代表整个表的B+树索引称为聚簇索引,根据主键列进行组织。聚簇索引数据结构的节点包含该行中所有列的值。二级索引结构的节点包含索引列和主键列的值。

    参考 https://dev.mysql.com/doc/refman/5.6/en/innodb-index-types.html 。

    每个InnoDB表都有一个称为聚簇索引的特殊索引,其中存储了行的数据。 通常,聚簇索引与主键的含义相同。为了在查询、插入或其他数据库操作中获得最佳性能,必须了解InnoDB如何使用聚簇索引对每个表的最常见的查找和DML操作进行优化。

    当在数据库表定义了主键时,InnoDB会将其作为聚簇索引使用。请为创建的数据库表都定义主键。如果数据库表没有逻辑上唯一且非空的列或一组列,请增加一个新的自增长且值会自动填充的列。

    如果没有为表定义主键,MySQL会找到第一个所有键列都非空的唯一索引,InnoDB会将它用作聚簇索引。

    如果表没有主键或合适的唯一索引,InnoDB会在包含行ID值的合成列内部生成名为GEN_CLUST_INDEX的隐藏聚簇索引。行按InnoDB分配给此类表中的行的ID排序。行ID是一个6字节的字段,随着新行的插入而单向增加。因此,通过行ID排序的列在物理上按插入顺序排列。

    除聚簇索引之外的所有索引都称为二级索引。 在InnoDB中,二级索引中的每条记录都包含该行的主键列以及二级索引指定的列。 InnoDB使用此主键值来搜索聚簇索引中的行。

    关于聚簇索引与二级索引中保存的内容,也可参考 https://dev.mysql.com/doc/refman/5.6/en/innodb-row-format.html 。

    参考《High Performance MySQL, 3rd Edition》关于聚簇索引与二级索引的示意图:

    以下为通过二级索引读取对应的聚簇索引,即行数据的示意图,图片来源 https://mariadb.com/kb/en/index-condition-pushdown/+image/index-access-2phases :

    4.5. 索引的顺序

    4.5.1. MySQL 8.0之前的版本

    在MySQL 8.0之前的版本中,索引记录以升序存储。

    参考 https://dev.mysql.com/doc/refman/5.6/en/create-index.html (5.7描述相同)。

    创建索引时可以ASC或DESC结尾。这些关键字可用于将来的扩展,以指定升序或降序索引值存储。目前,它们已被解析但被忽略;索引值始终以升序存储。

    4.5.2. MySQL 8.0之后的版本

    在MySQL 8.0之后的版本中,索引记录支持以升序或降序存储。

    参考 https://dev.mysql.com/doc/refman/8.0/en/create-index.html 。

    创建索引时可以ASC或DESC结尾,以指定索引值是以升序还是降序存储。如果未指定,则默认值为升序。

    参考 https://dev.mysql.com/doc/refman/8.0/en/descending-indexes.html 。

    MySQL(8.0)支持降序索引(descending index),索引定义中的DESC不再被忽略,会导致键值以降序存储。以前,索引可以以相反的顺序进行扫描,但会降低性能。降序索引可以按向前的顺序进行扫描,这样效率更高。

    使用降序索引后,使得当最有效的扫描顺序混合了某些升序列和其他降序列时,优化器也能使用多列索引(multiple-column indexes),即联合索引(composite indexes)。

    参考 https://dev.mysql.com/doc/relnotes/mysql/8.0/en/news-8-0-1.html 。

    MySQL从8.0.1版本开始支持降序索引。

    4.6. InnoDB索引B+树结构

    4.6.1. 页(page)

    参考 https://dev.mysql.com/doc/refman/5.6/en/glossary.html#glos_page 。

    页是表示InnoDB在磁盘(数据文件)和内存(缓冲池,buffer pool)之间一次传输多少数据的单位。 一个页可以包含一行或多行,取决于每一行中的数据量。如果一行不能完全容纳在单个页中,则InnoDB会设置其他指针式数据结构,以便有关该行的信息可以存储在一页中。

    参考 https://dev.mysql.com/doc/internals/en/innodb-page-structure.html 。

    InnoDB将所有记录存储在固定大小的单位内,该单位通常称为页,有时称为块。

    4.6.2. 页大小

    参考 https://dev.mysql.com/doc/refman/5.6/en/glossary.html#glos_page_size 。

    对于MySQL 5.5及以下版本,每个InnoDB页的大小固定为16 KB。该值表示一个平衡:足够大以容纳大多数行的数据,但足够小以最小化将不需要的数据传输到内存的性能开销。其他值未经测试或支持。

    从MySQL 5.6开始,InnoDB实例的页大小可以是4KB,8KB或16KB,由innodb_page_size配置选项控制。从MySQL 5.7.6开始,InnoDB还支持32KB和64KB页大小。对于32KB和64KB页大小,不支持ROW_FORMAT = COMPRESSED,最大记录大小为16KB。

    页大小在创建MySQL实例时设置,此后保持不变。相同的页大小适用于所有InnoDB表空间,包括system tablespace,file-per-table tablespaces,以及general tablespaces。

    较小的页大小可以帮助使用块大小较小的存储设备提高性能。

    参考 https://dev.mysql.com/doc/refman/5.6/en/innodb-parameters.html#sysvar_innodb_page_size 。

    innodb_page_size系统变量用于指定InnoDB表空间页大小。

    innodb_page_size只能在初始化MySQL实例之前进行配置,之后不能进行更改。如果未指定任何值,则使用默认页大小初始化实例。

    innodb_page_size默认值为16KB。

    4.6.3. 页的物理结构

    以下描述页在磁盘存储时的物理结构。

    参考 https://dev.mysql.com/doc/internals/en/innodb-page-overview.html 。

    InnoDB页包含以下7个部分:

    内容
    Fil Header
    Page Header
    Infimum + Supremum Records
    User Records
    Free Space
    Page Directory
    Fil Trailer

    Fil Header可以称为“File Page Header”。

    4.6.3.1. 文件页头(Fil Header)

    文件页头中包含了指向上一页与下一页的指针,即页之间构成了双向链表结构。

    参考 https://dev.mysql.com/doc/internals/en/innodb-fil-header.html 。

    文件页头中包含8个部分,其中FIL_PAGE_PREV为按键顺序的上一页的偏移量,FIL_PAGE_NEXT为按键顺序的下一页的偏移量。

    FIL_PAGE_PREV与FIL_PAGE_NEXT是页的后退和前进的指针。 以下为两层B+树的示例,说明上述指针。

                 --------
                 - root -
                 --------
                    |
          ----------------------
          |                    |
          |                    |
      --------             --------
      - leaf -     <-->    - leaf -
      --------             --------
    

    B+树的根页中的条目指向叶子页(如上图中的竖线“|”),叶子页也可以互相指向(如上图中水平双向指针“<–>”),这个特性使InnoDB可以在叶子页之间导航,不必返回到根级别。

    4.6.3.2. 页面头(Page Header)

    参考 https://dev.mysql.com/doc/internals/en/innodb-page-header.html 。

    页面头中包含名为“PAGE_N_DIR_SLOTS”的部分,大小为2字节,代表了页目录(Page Directory)中目录插槽的数量,初始值为2(下确界/上确界,即 Infimum/Supremum Records初始时分别对应一个插槽)。

    名为“PAGE_BTR_SEG_LEAF”的部分,为B+树中的叶子页的文件段头。

    名为“PAGE_BTR_SEG_TOP”的部分,为B+树中的非叶子页的文件段头。

    PAGE_BTR_SEG_LEAF与PAGE_BTR_SEG_TOP包含索引节点文件段的信息:表空间ID(space ID)、页编号(page number)、字节偏移(byte offset)。

    4.6.3.3. 下确界/上确界(Infimum/Supremum Records)

    参考 https://dev.mysql.com/doc/internals/en/innodb-infimum-and-supremum-records.html 。

    “Infimum”和“Supremum”是数学术语,指有序集合的外边界。下确界(infimum )是最大下界(GLB,Greatest Lower Bound),小于可能的最小键值。上确界是最小上限(LUB,Least Upper Bound),大于可能的最大键值。

    首次创建索引时,InnoDB会在根页中自动设置一个下确界记录和一个上确界记录,并且永远不会删除。它们在导航时是有用的屏障,因此“获取前一个”操作不会通过开头,“获取下一个操作”不会通过结尾。同样,下确界可以是临时记录锁定的虚拟目标。

    下确界记录和上确界记录可以视为索引页开销的一部分。最初它们都存在于根页上,随着索引的增长,下确界记录将存在于第一或最小叶子页上,下确界记录将存在于最后或最大键页上。

    4.6.3.4. 用户记录(User Records)

    用户记录中保存了用户插入数据库表的各行的记录数据,记录在存储时在物理上没有按照键的顺序排序,记录获取后的逻辑结构中按照键的顺序排序。

    参考 https://dev.mysql.com/doc/internals/en/innodb-user-records.html 。

    在页的用户记录部分中,可以找到用户插入的所有记录(record)。

    InnoDB不想根据B树的键顺序插入新行(这会涉及到大量数据转移,代价很大),因此 InnoDB会在现有行的结尾之后(在可用空间部分的顶部)或已删除行剩余的空间插入新行。

    根据B+树的定义,记录必须按键值顺序访问 ,因此每个记录中都有一个记录指针(Extra Bytes中的“next”字段,可参考后续对于记录的描述部分) ,该指针指向键顺序中的下一个记录,即 记录是单向链表InnoDB在搜索时可以按键顺序访问行。

    4.6.3.5. 页目录(Page Directory)

    页目录使得对页中的记录进行搜索时,可以进行二分查找。对比顺序链表查找元素的时间复杂度O(n),提高到接近O(logn)(实际情况需要更复杂的分析与计算)。

    参考 https://dev.mysql.com/doc/internals/en/innodb-page-directory.html 。

    页的页目录部分具有可变数量的记录指针。有时记录指针称为“插槽”或“目录插槽”。与其他DBMS不同,InnoDB不是每个页中的每个记录上都有一个插槽。InnoDB保留了一个稀疏目录。在满的页中,每六个记录有一个插槽。

    插槽可以跟踪记录的逻辑顺序(键的排序,不是按堆位置的顺序)。因此,如果记录为“A”“B”“F”“D”,则插槽将为(指向“A”的指针)(指向“B”的指针)(指向“D”的指针)(指向“F”的指针)。因为插槽是按键顺序排列的,并且每个插槽都有固定的大小,因此 很容易通过插槽对页上的记录进行二分查找。

    由于页目录没有为每个记录提供一个插槽,因此二分查找只能给出一个大概的位置,之后InnoDB必须跟随“下一个”记录指针。InnoDB的“稀疏插槽”策略也占用记录的“额外字节”部分中的n_owned字段:n_owned表示由于之前的记录没有自己的插槽,当前记录已通过了多少个记录。(即n_owned代表了有插槽的当前记录,及其之前没有插槽的记录的总记录数

    4.6.4. 行格式

    参考 https://dev.mysql.com/doc/refman/5.6/en/innodb-row-format.html 。

    表的行格式决定了行的物理存储方式,会影响查询和DML操作的性能。

    InnoDB存储引擎支持四种行格式:REDUNDANT,COMPACT,DYNAMIC和COMPRESSED(冗余,紧凑,动态和压缩)。

    InnoDB表的默认行格式为COMPACT。

    可以使用CREATE TABLE或ALTER TABLE语句中的ROW_FORMAT表选项显式定义表的行格式。示例如下:

    CREATE TABLE t1 (c1 INT) ROW_FORMAT=COMPACT;
    

    要创建使用DYNAMIC或COMPRESSED行格式的表,必须将innodb_file_format变量设置为Barracuda,并且必须启用innodb_file_per_table变量。如果未启用innodb_strict_mode,则将使用默认的COMPACT行格式创建InnoDB表。

    为了查看表的行格式,可使用“SHOW TABLE STATUS”或查询INFORMATION_SCHEMA.INNODB_TABLES表。示例如下:

    SHOW TABLE STATUS IN test1;
    
    SELECT NAME, ROW_FORMAT FROM INFORMATION_SCHEMA.INNODB_SYS_TABLES WHERE NAME='test1/t1';
    

    4.6.5. 记录的物理结构

    以下描述记录在磁盘存储时的物理结构。

    参考 https://dev.mysql.com/doc/internals/en/innodb-overview.html 。

    关于“原点”(Origin)的说明:

    记录的“原点”(Origin)或“零点”(Zero Point)是字段内容(Field Contents)的第一个字节,不是字段开始偏移量(Field Start Offsets)的第一个字节。如果有指向记录的指针,则该指针指向“原点”(Origin)。因此记录的前两部分(Field Start Offsets、Extra Bytes)通过对指针进行减操作来寻址,只有记录的第三部分(Field Contents)通过对指针进行加操作来寻址。

    记录的物理结构包括以下三部分:

    • 字段起始偏移量(Field Start Offsets)

    参考 https://dev.mysql.com/doc/internals/en/innodb-field-start-offsets.html 。

    字段起始偏移量包含了“字段开始的位置”信息的数字列表,其中每个条目都是相对于下一个字段开始处相对“原点”(Origin)的位置。条目的顺序是反的,即第一个字段的偏移量在列表的末尾。

    • 额外字节(Extra Bytes)

    参考 https://dev.mysql.com/doc/internals/en/innodb-extra-bytes.html 。

    额外字节是一个固定的6字节头。(参考 https://dev.mysql.com/doc/refman/5.6/en/innodb-row-format.html ,REDUNDANT行格式的记录头为6字节)

    在记录头中包含名为“deleted_flag”,大小为1比特,为1时代表记录已被删除。

    在记录头中包含名为“n_owned”,大小为4比特,代表该记录拥有的记录数(在页目录中会使用)。

    在记录头中包含名为“next”的部分,大小为2字节,为 指向页中下一条记录的指针 (对应前文“记录是单向链表”)。

    • 字段内容(Field Contents)

    参考 https://dev.mysql.com/doc/internals/en/innodb-field-contents.html 。

    记录的“字段内容”部分包含所有数据。字段按照定义顺序存储。

    字段之间没有标记(marker),并且记录的末尾没有标记或填充符(filler)。

    InnoDB在开始时会自动添加三个“系统列”(“system columns”)以进行内部管理。这些系统列是行ID(row ID),事务ID(transaction ID)和回滚指针(rollback pointer),它们的值现在不再重要,可视为三个黑盒。

    4.6.6. COMPACT行格式的记录结构

    参考 https://dev.mysql.com/doc/refman/5.6/en/innodb-row-format.html 。

    COMPACT行格式的部分存储特征如下:

    每个索引记录都包含一个5字节的记录头,该记录头之前可以有一个可变长度的头。记录头用于将连续的记录链接在一起,并用于行级锁定。

    记录头后跟着非NULL列的数据内容。

    聚簇索引中的记录包含所有用户定义列的字段。还有一个6字节的事务ID字段(transaction ID)和一个7字节的滚动指针字段(roll pointer)。

    每个二级索引记录中,包含在聚簇索引定义的,不在二级索引中的所有主键列。

    以下参考 https://blog.jcole.us/2013/01/10/the-physical-structure-of-records-in-innodb/ ,图片来源 https://github.com/jeremycole/innodb_diagrams 。

    4.6.6.1. 聚簇索引-叶子(leaf)页记录格式

    聚簇索引-叶子页记录格式示例如下所示:

    聚簇索引-叶子页记录的Cluster Key Fields保存了聚簇键字段。

    聚簇索引-叶子页记录的Non-Key Fields保存所有非索引键字段(Non-Key Fields,即所有非PRIMARY KEY字段的实际行数据)。

    4.6.6.2. 聚簇索引-非叶子(non-leaf)页记录格式

    聚簇索引-非叶子页记录格式示例如下所示:

    聚簇索引-非叶子页记录的Cluster Key Min保存了孩子页中键的最小值。

    B+树的非叶子节点不保存实际的数据,因此聚簇索引-非叶子页记录不包含非索引键字段,在Child Page Number中保存了孩子页的序号(指向孩子页的指针)。

    4.6.6.3. 二级索引-叶子页记录格式

    二级索引-叶子页记录格式示例如下所示:

    二级索引-叶子页记录的Secondary Key Fields保存了二级索引键字段。

    二级索引-叶子页记录的Cluster Key Fields保存了二级索引键对应的聚簇索引键字段。

    4.6.6.4. 二级索引-非叶子页记录格式

    二级索引-非叶子页记录格式示例如下所示:

    二级索引-非叶子页记录的Secondary Key Min保存了孩子页中键的最小值。

    二级索引-非叶子页记录的Child Page Number保存了孩子页的序号(指向孩子页的指针)。

    4.6.7. InnoDB索引B+树逻辑结构

    以下描述页被读取到内存后的逻辑结构。

    参考 https://blog.jcole.us/2013/01/10/btree-index-structures-in-innodb/ 。

    页被称为“叶子”页或“非叶子”页(在某些情况下也称为“内部”或“节点”页)。叶子页包含实际的行数据。非叶子页仅包含指向其他非叶子页或叶子页的指针。树是平衡的,因此树的所有分支具有相同的深度。

    InnoDB为树中的每个页分配一个“级别”:叶子页被分配为级别0,级别在树上递增。根页的级别基于树的深度。

    对于叶子页和非叶子页,每个记录(包括下确界和上确界系统记录)都包含“下一条记录”指针,该指针存储下一条记录(在页内)的偏移量。链表从下确界开始, 并按键升序链接所有记录 ,在上确界终止。记录在页内没有进行物理排序(插入时会占用任意可用空间);它们的唯一顺序源自它们在链表中的位置。

    4.6.7.1. 叶子页

    叶子页的简化示例如下所示:

    叶子页包含非索引键值,作为每个记录中包含的“数据”的一部分。

    4.6.7.2. 非叶子页

    非叶子页的简化示例如下所示:

    非叶子页的结构与叶子页类似,但非叶子节点不包含非索引键字段(Non-Key Fields),保存的“数据”是孩子页的页编号。

    非叶子页也没有保存具体的键,而是保存孩子页中最小的键值。

    4.6.7.3. B+树层级示例

    InnoDB索引B+树层级简化示例如下所示:

    大多数索引包含多个页,因此多个页按升序和降序链接在一起。

    每个页(在FIL header中)都包含指向“上一页”和“下一页”的指针,对于索引页,它们用于形成同一级别的页的双向链表。

    4.6.7.4. B+树结构示例

    InnoDB索引B+树结构简化示例如下所示:

    每个级别的所有页都相互双向链接,并且在每个页内,记录按升序单向链接。非叶子页包含“指针”(包含孩子页编号),而不是非索引键的行数据。

    4.6.8. 页目录结构示例

    参考 https://blog.jcole.us/2013/01/14/efficiently-traversing-innodb-btrees-with-the-page-directory/ 。

    4.6.8.1. 页目录的用意

    索引页中的所有记录都按升序在单向链表中链接在一起。 对于可能包含数百条记录的页,遍历链表的代价很大:必须比较每个记录的键,并且这需要在B+树的每个级别上进行,直到在叶子页找到要查找的记录为止。

    页目录使用以下方法,极大地优化了以上搜索场景:提供一个固定宽度的数据结构,该结构具有按顺序指向每4-8条记录中的1条的直接指针。可用于对每个页中的记录进行传统的二分查找。由于页目录实际上是一个数组,当记录按升序链接时,也可以按升序或降序遍历。

    4.6.8.2. 页目录物理结构

    页目录物理结构示例如下:

    插槽数量(页目录长度)在页面头的第一个字段中指定。页目录始终包含一个下确界和上确界系统记录的条目(因此最小大小为2个条目,即插槽),并且可能包含0个或多个其他条目,每4-8个系统记录对应一个插槽。

    当某条记录在页目录中代表了另一条记录时,则称为某条记录“拥有”(“own”)另一条记录。页目录中的每个条目都“拥有”该页目录中的上一个条目之间的记录,直到其自身为止。每个记录“拥有”的记录数存储在每个记录之前的记录头中。

    4.6.8.3. 页目录逻辑结构

    页目录逻辑结构如下图下半部分所示(包含一页中键值从0至23的24个记录),红色虚线代表了页目录中的插槽与页中记录的对应关系:

    记录被单向链接,从下确界记录,到上确界记录,再到用户记录。

    部分记录会被输入到页目录中,在图中以粗体显示,并在其顶部的页目录数组中注明其偏移量。

    4.6.9. B+树树高与记录数

    参考 https://blog.jcole.us/2013/01/10/btree-index-structures-in-innodb/ 。

    以下为B+树索引效率的示例。

    假设记录的填充是完美的(每页都满了,在实践中永远不会发生,但是对于讨论很有用)。在示例中,InnoDB中针对简单表的B+树索引能够在每个叶子页存储468条记录,或者在每个非叶子页存储1203条记录。 在以上条件下,索引B+树在给定的树高下可以是以下大小的最大值:

    树高非叶子页数量叶子页数量行数大小(字节数)
    10146816.0 KiB
    211203> 563 thousand18.8 MiB
    312041447209> 677 million22.1 GiB
    414484131740992427> 814 billion25.9 TiB

    4.7. InnoDB限制

    关于InnoDB限制的表、索引等限制,参考 https://dev.mysql.com/doc/refman/5.6/en/innodb-limits.html 。

    • 列数量限制

    一个表可以包含的最大列数量为1017(早期限制为1000,从MySQL 5.6.9开始增加到上述数量)。

    • 二级索引数量限制

    一个表可以包含的最大二级索引数量为64。

    • 索引键前缀长度限制

    默认情况下,索引键前缀(index key prefix)长度限制为767个字节。例如,假设使用utf8mb3字符集且每个字符最多3个字节,则在TEXT或VARCHAR类型的列使用超过255个字符的列前缀索引可能会达到此限制。启用innodb_large_prefix配置选项后,对于使用DYNAMIC或COMPRESSED行格式的InnoDB表,索引键前缀长度限制将提高到3072字节。

    如果在创建MySQL实例时通过指定innodb_page_size选项将InnoDB页大小减小为8KB或4KB,则基于16KB页大小的3072个字节的限制,将按比例减小索引键的最大长度。即当页大小为8KB时,最大索引键长度为1536字节;当页大小为4KB时,最大索引键长度为768字节。

    适用于索引键前缀的限制也适用于全列索引键(full-column index key)。

    • 多列索引列数量限制

    一个多列索引可以包含的最大列数量为16。

    • 行大小限制

    除页外(off-page)存储的可变长度列(variable-length column)外,最大行大小略小于页大小的一半。对于默认页大小16KB,最大行大小约为8000字节。如果在创建MySQL实例时通过指定innodb_page_size选项来减小页大小,则对于大小为8KB的页,最大行大小为4000字节,对于大小为4KB的页,最大行大小为2000字节。LONGBLOB和LONGTEXT列必须小于4GB,包括BLOB和TEXT列在内的总行大小必须小于4GB。

    如果一行的长度少于一页的一半,则该行全部存储在当前页内。如果一行的长度超过半页,则将选择可变长度的列在外部的页外存储,直到该行适合半页为止。

    根据以上限制可知, 一个InnoDB索引页中,至少会包含两条记录。

    4.8. 记录中可变长度列存储位置

    参考 https://dev.mysql.com/doc/refman/5.6/en/innodb-row-format.html 。

    将列值存储在B+树索引节点中的规则包含例外情况,即可变长度列。可变长度列太长,无法容纳在B+树页上,而是存储在单独分配的磁盘页中,这些磁盘页称为溢出页(overflow page)。这些列称为页外列(off-page column)。页外列的值存储在溢出页的单向链表中,每个这样的列都有其自己的一个或多个溢出页的列表。根据列的长度,可变长度列值的全部或前缀存储在B+树中,以避免浪费存储空间并不得不读取单独的页。

    • COMPACT与REDUNDANT行格式

    使用COMPACT或REDUNDANT行格式时,将可变长度列保存在外部的页外存储,InnoDB在当前行中存储前768个字节,剩余部分存储在外部的溢出页中。每个此类列都有其自己的溢出页列表。长度为768字节的前缀附带一个20字节的值,该值存储列的真实长度,并指向溢出列表中存储的该列的剩余部分。

    如果列值的长度小于或等于768个字节,则不使用溢出页,并且由于该值完全存储在B+树节点中,因此可以节省一些I/O。这对于较短的BLOB列值非常有效,但是可能导致B+树节点填充较多的数据而不是键值,从而降低效率。具有很多BLOB列的表可能导致B+树节点变得太满,并且包含的行太少,这使得整个索引的效率变低,相比行的长度更短或列值存储在页外的情况。

    • DYNAMIC与COMPRESSED行格式

    对于使用DYNAMIC行格式的表,InnoDB可以完全在页外存储长度很长的可变长度列值(对于VARCHAR,VARBINARY,BLOB和TEXT类型),聚簇索引记录仅包含指向溢出页的20字节指针。对于固定长度字段,若长度大于或等于768字节,会被编码为可变长度字段。

    列是否存储在页外取决于页大小和行的总大小。当一行太长时,将选择最长的列进行页外存储,直到聚簇索引记录适合B+树页为止。小于或等于40个字节的TEXT和BLOB列存储在行中。

    DYNAMIC和COMPRESSED行格式支持最大3072字节的索引键前缀。该功能由innodb_large_prefix变量控制,该变量默认情况下被禁用。

    关于记录中可变长度列存储位置,也可参考 https://dev.mysql.com/doc/refman/5.6/en/innodb-file-space.html 。

    4.9. 记录中的NULL列

    • REDUNDANT行格式

    当使用REDUNDANT行格式时,记录中包含一个指向该记录的每个字段的指针。如果记录中字段的总长度小于128个字节,则指针为1个字节;否则为两个字节。指针数组称为记录目录(record directory)。指针指向的区域是记录的数据部分。

    NULL值在记录目录中保留一个或两个字节。当存储在可变长度列中时,NULL值在记录的数据部分中保留零字节。对于固定长度的列,该列的固定长度保留在记录的数据部分。为NULL值保留固定空间允许将列从NULL值更新为非NULL值,而不会引起索引页碎片。

    • COMPACT、DYNAMIC与COMPRESSED行格式

    当使用COMPACT、DYNAMIC或COMPRESSED行格式时,记录头的可变长度部分包含一个用于指示NULL列的位向量(bit vector)。如果索引中可为NULL的列数为N,则位向量占用CEILING(N/8)个字节(CEILING函数为向上舍入)。NULL列不占用此位向量以外的空间。记录头的可变长度部分还包含可变长度列的长度。每个长度占用一个或两个字节,取决于列的最大长度。如果索引中的所有列都不为NULL并且具有固定长度,那么记录头将没有可变长度部分。

    4.10. 页分裂与页合并

    参考 https://dev.mysql.com/doc/refman/5.6/en/index-page-merge-threshold.html 。

    从MySQL 5.7.6开始,可以为索引页配置MERGE_THRESHOLD值。如果在删除行或通过UPDATE操作使行变短时,索引页的“页充满程度”(“page-full”)百分比低于MERGE_THRESHOLD值,则InnoDB会尝试将索引页与相邻的索引页合并。 MERGE_THRESHOLD的默认值为50(以前的硬编码值),最小值为1,最大值为50。

    当索引页的“页充满程度”百分比低于50%(默认的MERGE_THRESHOLD设置)时,InnoDB会尝试将索引页与相邻页合并。如果两个页都接近50%充满,则页合并后可能会很快发生页分裂(page split)。如果页的合并与分裂行为频繁发生,则可能会对性能产生不利影响。

    后续内容将对频繁页分裂对INSERT操作的影响进行对比验证。

    5. InnoDB索引存储相关

    5.1. file-per-table表空间

    参考 https://dev.mysql.com/doc/refman/5.6/en/innodb-file-per-table-tablespaces.html 。

    file-per-table空间包含单个InnoDB表的数据和索引,并存储在文件系统单独的数据文件中。

    InnoDB默认在file-per-table表空间中创建表,由innodb_file_per_table变量控制,禁用innodb_file_per_table会导致InnoDB在系统表空间中创建表。

    file-per-table表空间会创建在MySQL data目录的schema目录中的.ibd数据文件中。例如在名为“testdb”的schema中创建数据库表test_table,会在MySQL的data/testdb目录中创建test_table.ibd文件。

    5.2. InnoDB索引物理结构

    参考 https://dev.mysql.com/doc/refman/5.6/en/innodb-physical-structure.html 。

    所有的InnoDB索引都是B+树,索引记录存储在树的叶子页中。索引页的默认大小为16KB。

    可以在初始化MySQL实例之前设置innodb_page_size配置选项来定义MySQL实例中所有InnoDB表空间的页大小。定义实例的页大小后,只有在重新初始化实例时能够修改。支持的页大小为16KB,8KB和4KB。

    5.3. InnoDB表元文件(.frm)

    参考 https://dev.mysql.com/doc/refman/5.6/en/innodb-data-dictionary.html 、 https://dev.mysql.com/doc/refman/5.6/en/using-innodb-tables.html#innodb-frm-file 。

    InnoDB数据字典包含用于跟踪对象(例如表,索引和表列)的元数据。

    MySQL将表的数据字典信息存储在数据库目录中的.frm文件中。与其他MySQL存储引擎不同,InnoDB还将表在自身内部数据字段中的信息编码在系统表空间中。当MySQL删除表或数据库时,它将删除一个或多个.frm文件以及InnoDB数据字典中的相应条目。

    6. InnoDB索引读取方式

    6.1. Buffer Pool

    Buffer Pool对索引的读操作进行缓存,可以减少I/O次数,提高效率。

    参考 https://dev.mysql.com/doc/refman/5.6/en/innodb-buffer-pool.html 。

    buffer pool是主内存中的一个区域,InnoDB在访问表和索引数据时会在其中进行缓存。buffer pool允许直接从内存中处理经常使用的数据,从而加快处理速度。在专用服务器上,通常将多达80%的物理内存分配给buffer pool。

    为了提高大容量读取操作的效率,buffer pool被分为多个页,这些页可以潜在容纳多行。为了提高缓存管理的效率,buffer pool被实现为页的链表形式。很少使用的数据会从缓存中过期,使用LRU算法的变体。

    参考 https://dev.mysql.com/doc/refman/5.6/en/innodb-buffer-pool-flushing.html 。

    InnoDB在后台执行某些任务,包括从buffer pool中刷新脏页。 脏页是指已被修改但尚未写入磁盘数据文件的页。

    Buffer Pool的示意图如下所示:

    6.2. Change Buffer

    Change Buffer对索引的写操作进行缓存,可以减少I/O次数,提高效率。

    参考 https://dev.mysql.com/doc/refman/5.6/en/innodb-change-buffer.html 。

    change buffer是一种特殊的数据结构,当二级索引页不在buffer pool中时,对二级索引页的修改进行缓存。被缓冲的修改可能由INSERT,UPDATE或DELETE等DML操作引起,在以后通过其他读取操作将页加载到buffer pool中时会被合并。

    当对表执行INSERT,UPDATE和DELETE操作时,索引列的值(尤其是二级索引键值)通常处于未排序的顺序,需要大量的I/O才能使二级索引保持最新状态。当相关页不在buffer pool中时,change buffer会将修改缓存到二级索引条目中,通过不立即从磁盘读取页来避免昂贵的随机I/O操作。当页加载到buffer pool中时,缓冲的更改将合并,更新的页随后将刷新到磁盘。当服务器接近闲置时以及在缓慢关闭期间,InnoDB主线程会合并缓冲的更改。

    可以使用innodb_change_buffering配置参数来控制InnoDB执行change buffer的范围。可以为插入(insert),删除操作(delete,最初将索引记录标记为删除)和清除操作(purge,物理删除索引记录)启用或禁用缓冲。更新(update)操作是插入和删除的组合。

    默认的innodb_change_buffering值为all,即对上述插入,删除和清除操作进行缓冲。

    Change Buffer的示意图如下所示:

    参考 http://mysql.taobao.org/monthly/2015/07/01/ ,对于唯一二级索引(unique key),由于索引记录具有唯一性,因此无法缓存插入操作,但可以缓存删除操作。即Change Buffer对于唯一二级索引仅支持删除操作。

    7. InnoDB架构图

    参考 https://dev.mysql.com/doc/refman/5.6/en/innodb-architecture.html 。

    InnoDB架构图如下所示,包含内存与磁盘中的结构:

    8. MySQL源码

    MySQL源码地址为 https://github.com/mysql/mysql-server 。

    MySQL的源码可与文档中的说明相互印证,示例如下:

    https://github.com/mysql/mysql-server/blob/5.6/storage/innobase/include/btr0btr.ic 文件中定义了btr_page_set_next、btr_page_set_prev方法,分别用于设置下一个/上一个索引页字段。

    https://github.com/mysql/mysql-server/blob/5.6/storage/innobase/btr/btr0btr.cc 文件中调用了btr_page_set_next、btr_page_set_prev方法,以上两个方法在调用时成对出现。

    https://github.com/mysql/mysql-server/blob/5.6/storage/innobase/include/page0page.ic 文件中定义了page_rec_is_infimum方法,当输入参数为页中的下确界记录时,返回TRUE;调用当前文件中的page_rec_is_infimum_low方法。还定义了page_rec_is_supremum方法,当输入参数为页中的上确界记录时,返回TRUE;调用当前文件中的page_rec_is_supremum_low方法。

    https://github.com/mysql/mysql-server/blob/5.6/storage/innobase/include/page0cur.ic 文件中定义了page_cur_is_before_first方法,当游标在页中第一个用户记录之前时,返回TRUE;调用上述page_rec_is_infimum方法。还定义了page_cur_is_after_last方法,当游标在页中最后一个用户记录之后时,返回TRUE;调用上述page_rec_is_supremum方法。

    https://github.com/mysql/mysql-server/blob/5.6/storage/innobase/include/rem0rec.ic 文件中定义了rec_get_next_ptr方法,获取并返回同一页中下一条链接的记录的指针,调用当前文件中的rec_get_next_ptr_const方法。

    9. 参考资料

    以上参考的资料如下:

    https://dev.mysql.com/doc/refman/5.6/en/

    https://dev.mysql.com/doc/internals/en/

    https://blog.jcole.us/innodb/

    http://mysql.taobao.org/monthly/

    《High Performance MySQL, 3rd Edition》

    展开全文
  • 使用innodb_ruby探查Innodb索引结构  innodb_ruby 是使用 Ruby 编写的 InnoDB 文件格式解析器。innodb_ruby 的目的是暴露一些其他隐藏的 InnoDB 原理。  innodb_ruby不适合使用于生产环境,但可以作为学习...

      innodb_ruby 是使用 Ruby 编写的 InnoDB 文件格式解析器。innodb_ruby 的目的是暴露一些其他隐藏的 InnoDB 原理。

      innodb_ruby不适合使用于生产环境,但可以作为学习工具来使用。

    https://blog.jcole.us/2013/01/03/a-quick-introduction-to-innodb-ruby/

     

     

    转载于:https://www.cnblogs.com/DataArt/p/9961013.html

    展开全文
  • 【mysql】MyISAM和InnoDB索引结构分析

    千次阅读 2019-08-22 09:47:31
    MyISAM和InnoDB索引结构分析 一、存储引擎作用于什么对象 存储引擎是作用在表上的,而不是数据库。 二 MyISAM和InnoDB对索引和数据的存储在磁盘上是如何体现的 先来看下面创建的两张表信息,role表使用的存储...

    MyISAM和InnoDB索引结构分析

    一、存储引擎作用于什么对象

    存储引擎是作用在表上的,而不是数据库。

    二 MyISAM和InnoDB对索引和数据的存储在磁盘上是如何体现的

    先来看下面创建的两张表信息,role表使用的存储引擎是MyISAM,而user使用的是InnoDB:

    再来看下两张表在磁盘中的索引文件和数据文件:

    1. role表有三个文件,对应如下:

    role.frm:表结构文件
    role.MYD:数据文件(MyISAM Data)
    role.MYI:索引文件(MyISAM Index)
    2. user表有两个文件,对应如下:

    user.frm:表结构文件
    user.ibd:索引和数据文件(InnoDB Data)
    也由于两种引擎对索引和数据的存储方式的不同,我们也称MyISAM的索引为非聚集索引,InnoDB的索引为聚集索引

    三 MyISAM主键索引与辅助索引的结构

    我们先列举一部分数据出来分析,如下:

    上面已经说明了MyISAM引擎的索引文件和数据文件是分离的,我们接着看一下下面两种索引结构异同。

    1. 主键索引:

    上一篇文章已经介绍过数据库索引是采用B+Tree存储,并且只在叶子节点存储数据,在MyISAM引擎中叶子结点存储的数据其实是索引和数据的文件指针两类。

    如下图中我们以Col1列作为主键建立索引,对应的叶子结点储存形式可以看一下表格。

    通过索引查找数据的流程:先从索引文件中查找到索引节点,从中拿到数据的文件指针,再到数据文件中通过文件指针定位了具体的数据。

    2. 辅助(非主键)索引:

    以Col2列建立索引,得到的辅助索引结构跟上面的主键索引的结构是相同的。

     
    四 InnoDB主键索引与辅助索引的结构

    1. 主键索引:

    我们已经知道InnoDB索引是聚集索引,它的索引和数据是存入同一个.idb文件中的,因此它的索引结构是在同一个树节点中同时存放索引和数据,如下图中最底层的叶子节点有三行数据,对应于数据表中的Col1、Col2、Col3数据项。

    2. 辅助(非主键)索引:

    这次我们以数据表中的Col3列的字符串数据建立辅助索引,它的索引结构跟主键索引的结构有很大差别,我们来看下面的图:

    在最底层的叶子结点有两行数据,第一行的字符串是辅助索引,按照ASCII码进行排序,第二行的整数是主键的值。

    五 InnoDB索引结构需要注意的点

    1. 数据文件本身就是索引文件

    2. 表数据文件本身就是按B+Tree组织的一个索引结构文件

    3. 聚集索引中叶节点包含了完整的数据记录

    4. InnoDB表必须要有主键,并且推荐使用整型自增主键

    正如我们上面介绍InnoDB存储结构,索引与数据是共同存储的,不管是主键索引还是辅助索引,在查找时都是通过先查找到索引节点才能拿到相对应的数据,如果我们在设计表结构时没有显式指定索引列的话,MySQL会从表中选择数据不重复的列建立索引,如果没有符合的列,则MySQL自动为InnoDB表生成一个隐含字段作为主键,并且这个字段长度为6个字节,类型为整型。

    那为什么推荐使用整型自增主键而不是选择UUID?

    UUID是字符串,比整型消耗更多的存储空间;
    在B+树中进行查找时需要跟经过的节点值比较大小,整型数据的比较运算比字符串更快速;
    自增的整型索引在磁盘中会连续存储,在读取一页数据时也是连续;UUID是随机产生的,读取的上下两行数据存储是分散的,不适合执行where id > 5 && id < 20的条件查询语句。
    在插入或删除数据时,整型自增主键会在叶子结点的末尾建立新的叶子节点,不会破坏左侧子树的结构;UUID主键很容易出现这样的情况,B+树为了维持自身的特性,有可能会进行结构的重构,消耗更多的时间。
    为什么非主键索引结构叶子节点存储的是主键值?
    保证数据一致性和节省存储空间,可以这么理解:商城系统订单表会存储一个用户ID作为关联外键,而不推荐存储完整的用户信息,因为当我们用户表中的信息(真实名称、手机号、收货地址···)修改后,不需要再次维护订单表的用户数据,同时也节省了存储空间。
     

    展开全文
  • InnoDB索引使用的是B+树。 索引分为:主键索引和非主键索引(二级索引) 主键索引(聚簇索引) InnoDB通过主键聚集数据,下图中被索引的列就是主键。 聚簇索引优点: 聚簇索引缺点: 二级索引 下面是...
  • Innodb 索引结构了解

    千次阅读 2010-09-27 12:04:00
    每个Innodb表的数据其实可以说就是以一个树型(B-Tree)结构存储的,表的数据和主键(Primary Key)共同组成了一个索引结构,也就是我们常说的Innodb的Clustered Primary Key。在这个Clustered Primary Key中...
  • Innodb 作为 MySQL 中使用...每个Innodb表的数据其实可以说就是以一个树型(B-Tree)结构存储的,表的数据和主键(PrimaryKey)共同组成了一个索引结构,也就是我们常说的Innodb的Clustered Primary Key。在这个Clust
  • MySQL存储引擎MyISAM和InnoDB底层索引结构

    万次阅读 多人点赞 2018-10-10 11:29:36
    目录 一 存储引擎作用于什么对象 二 MyISAM和InnoDB对索引和数据的存储在磁盘上是如何体现的 ...五 InnoDB索引结构需要注意的点 PS:为了更好地理解本文内容,我强烈建议先阅读完我的上一篇文章...
  • 三、MyIsam主键索引和辅助索引(非主键索引)的结构1、主键索引2、辅助索引(非主键)索引四、InnoDB主键索引与辅助索引的结构1、主键索引2、辅助(非主键)索引五、InnoDB索引结构需要注意的点 一、存储引擎作用于...
  • InnoDB索引结构

    千次阅读 2021-09-17 10:31:19
    InnoDB是一个将表中的数据存储到磁盘上的存储引擎,所以即使关机后重启我们的数据还是存在的。而真正处理数据的过程是发生在内存中的,所以需要把磁盘中的数据加载到内存中,如果是处理写入或修改请求的话,还需要把...
  • InnoDB索引结构 索引的定义 MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构。 就像我们想在新华字典去查找一个字,我们会在目录页寻找这个字的拼音首字母或者偏旁部首,以...
  • InnoDB索引

    万次阅读 2019-08-05 16:30:09
    InnoDB存储引擎支持一下几种索引 B+ 树索引 全文索引 哈希索引 2.B+ 树索引 B+ 树索引并不能找到给定字符的具体位置,而是将字符所在的页读取到内存中,然后再内存中查找数据。B+树中的B不是代表二叉(binary), ...
  • mysql innodb 索引文件结构 http://blog.csdn.net/u012978884/article/details/52416997
  • 3.InnoDB索引

    万次阅读 多人点赞 2021-08-19 10:54:46
    InnoDB索引
  • innodb的b+树索引结构

    2019-09-08 09:29:53
    一、innodb索引结构为什么是树结构,不是hash结构。 hash索引,时间复杂度为O(1),平衡二叉树的时间复杂度为O(lg(n))。但是由于sql查询数据,很多都是范围查询,而树是有序的,hash是无序的,hash定位不到范围数据,...
  • InnoDB 索引的物理结构

    2019-12-03 22:09:38
    除空间索引(spatial indexes)外,InnoDB索引是B树数据结构。 空间索引使用R树,R树是用于索引多维数据的专用数据结构。 索引记录存储在其B树或R树数据结构的叶页中。 索引页的默认大小为16KB。 当新记录插入到...
  • InnoDB的数据结构
  • 一文搞定InnoDB索引

    2020-12-14 12:01:46
    关于InnoDB索引及相关知识的个人理解,如遇错误欢迎指正。 目录InnoDB的索引聚集索引(clustered index)普通索引(secondary index)回表是什么覆盖索引/索引覆盖(covering index)回到普通索引(Secondary indexes)索引...
  • 2、InnoDB索引数据结构 1)B-Tree 在看B+Tree之前,我们先看看B-Tree B-Tree是一种为外查找(磁盘类外存储设备,数据量太大不能全放在内存里)而设计的平衡多叉树。那为什么用B树而不用其他的如二叉树、平衡二叉树呢...
  • DML对innodb索引的影响

    千次阅读 2013-12-31 16:20:16
    首先需要了解一下innodb索引结构,关键下面几点: 1,索引结构是B+tree; 2,主键索引的索引结构和数据一起,即数据放到主键索引B+tree的叶子节点中; 3,辅助索引的索引结构也是B+tree,但叶子节点存储关键字和...
  • 数据结构索引-InnoDB索引

    千次阅读 2016-05-26 07:38:07
    InnoDB中,数据文件本身就是索引文件,表文件本身就是一个按照B+树组织的一个索引结构,叶节点data保存了完整的数据记录,这个索引的key是数据表的主键,因此InnoDB表数据文件本身就是主索引。   ...
  • 在本文中,我们以 InnoDB 为例,介绍 MySQL 的索引结构以及其使用 B+ 树实现索引的原因。 表空间 首先,来了解一下 MySQL 的表空间。中的所有数据被存储在一个空间内,称之为表空间,表空间内部又可以分为段(segment...
  • MyISAM与InnoDB索引结构 现在我们硬盘上的数据,基本上都是使用B+Tree数据结构来进行存储数据的。 1、非聚簇(集)结构 MyISAM主键索引有二个文件,有一个是索引文件(以 .MYI 结尾),一个是数据文件(以 .MYD...
  • 14.8.2.2 InnoDB索引的物理结构 除空间索引外,InnoDB索引是B树数据结构。空间索引使用R树,这是用于索引多维数据的专用数据结构。索引记录存储在B树或R树数据结构的叶节点的页中。索引页的默认大小是16KB。 将新...
  • InnoDB索引

    2019-10-06 08:03:30
    InnoDB索引实现 虽然InnoDB也使用B+Tree作为索引结构,但具体实现方式却与MyISAM截然不同。 第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道,MyISAM索引文件和数据文件是分离的,索引文件仅保存...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 90,167
精华内容 36,066
关键字:

innodb索引结构