首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >B+Tree index structures in InnoDB(7.InnoDB中B+树的索引结构)

B+Tree index structures in InnoDB(7.InnoDB中B+树的索引结构)

作者头像
冬天里的懒猫
发布2020-08-26 10:11:32
7540
发布2020-08-26 10:11:32
举报

这篇文章引用的是2014年2月3日的innodb_ruby 0.8.8版本。 在《学习InnoDB:核心之旅》中,我介绍了innodb_diagrams项目来描述InnoDB的内部结构,它提供了这篇文章中用到的所有图表。在对innodb_ruby的快速介绍一文中,我介绍了innodb_space命令行工具的安装和一些快速演示。 在InnoDB索引页的物理结构中描述了InnoDB索引页的物理结构。现在,我们将通过一些实际示例来研究InnoDB如何在逻辑上构造索引。

B+树的一些术语:根、叶子和层

InnoDB中使用B+树结构做为索引。当数据不能装入内存并且必须从磁盘读取的时候,B+树特别有效。因为它确保访问请求的任何数据都需要固定的最大读取次数。这只基于树的深度,而树的深度可以很好的伸缩。 索引树从一个根页面开始,它的位置是固定的,永久存储在InnoDB的数据字典中。做为访问该树的起点。树可以像当个根页面一样小,也可以像多层树种百万个页面一样大。 页面被分为叶子页和非叶子页(在某些上下文中也被称为内部或者节点页面)。叶子页中包含实际的行数据,非叶子页只包含指向其它非叶子页或者叶子页的指针。这棵树是平衡的。所有树的分支都具有相同的深度。 InnoDB给树中的每个页面都分配一个级别,叶子页面被分配为0级,级别在树种递增。根页面级别基于树的深度。如果区别很重要的话,所有既不是叶子页面也不是根页面的页都可以称为内部页面。

叶子页和非叶子页

对于叶子页和非叶子页,每个记录包括infimum和supremum的系统记录。在页面中,都包含一个指向下一个记录的指针。它存储下一个记录的offset。该链表从infimum开始,按key的升序链接所有记录,到supermum结束。这些记录并不是在页面中安物理顺序排列的,他们在插入的时候占用的可用的空间。他们唯一的顺序来自于他们在链表中的位置。 叶子页面包含的非键值做为数据的一部分,包含在每个记录中。

在这里插入图片描述
在这里插入图片描述

非叶子页面具有相同的结构,但不是非key字段,他们的data是子页面的页码,不是确切的键,而是他们所指向的子页面上的最小值。

在这里插入图片描述
在这里插入图片描述

同一级别的页

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

在这里插入图片描述
在这里插入图片描述

每个页上都有一个上一页和下一页的指针,在页眉中,这些指针用于索引页面,用于形成相同级别页面的双向链表。

单页表详情

让我们来看看B+树在一个单一的索引页面中涉及的大部分内容。

在这里插入图片描述
在这里插入图片描述
创建并填充表

上图中使用的测试表可以创建和填充,确保你使用的是innodb_file_per_table和Barracuda文件格式:

CREATE TABLE t_btree (
  i INT NOT NULL,
  s CHAR(10) NOT NULL,
  PRIMARY KEY(i)
) ENGINE=InnoDB;

INSERT INTO t_btree (i, s)
  VALUES (0, "A"), (1, "B"), (2, "C");

虽然这个表非常小而且不真实,但是它确实能很好的演示记录和记录遍历如何工作。

验证空间文件的基本机构

该表应该与我们之前研究的表相匹配,其中包含三个标准开销页。FSP_HDR、IBU_BITMAP和INODE,后面是一个用于根索引的索引页。在本例中式两个未使用的已分配页。

$ innodb_space -f t_btree.ibd space-page-type-regions
start       end         count       type                
0           0           1           FSP_HDR             
1           1           1           IBUF_BITMAP         
2           2           1           INODE               
3           3           1           INDEX               
4           5           2           FREE (ALLOCATED)    

space-index-pages-summary 模式将显示预期的三条数据:

$ innodb_space -f t_btree.ibd space-index-pages-summary
page        index   level   data    free    records 
3           18      0       96      16156   3       
4           0       0       0       16384   0       
5           0       0       0       16384   0    

注意,space-index-pages-summary将空页进行显示。这通常用于画图。 空间索引模式将显示关于我们的主键索引的统计数据,它在其内部文件段上消耗一个页面:

$ innodb_space -f t_btree.ibd space-indexes
id          root        fseg        used        allocated   fill_factor 
18          3           internal    1           1           100.00%     
18          3           leaf        0           0           0.00%     
设置record describer

为了让innodb_ruby解析记录的内容,我们需要提供一个记录描述器,他只是要给ruby类,提供了一个返回索引描述的方法。

class SimpleTBTreeDescriber < Innodb::RecordDescriber
  type :clustered
  key "i", :INT, :NOT_NULL
  row "s", "CHAR(10)", :NOT_NULL
end

我们需要注意的是,这是联合键,为键提供列描述,为非键字段提供列描述,有必要要求innodb_space 用以下附加参数加载这个类:

-r -r ./simple_t_btree_describer.rb -d SimpleTBTreeDescriber
查看记录内容

本例中的根页面可以使用页面转储模式转储,并为根页面提供页码:

$ innodb_space -f t_btree.ibd -r ./simple_t_btree_describer.rb -d SimpleTBTreeDescriber -p 3 page-dump

除了我们之前看到的部分输出之外,它现在会打印要给records部分,每条记录的结构如下:

{:format=>:compact,
 :offset=>125,
 :header=>
  {:next=>157,
   :type=>:conventional,
   :heap_number=>2,
   :n_owned=>0,
   :min_rec=>false,
   :deleted=>false,
   :field_nulls=>nil,
   :field_lengths=>[0, 0, 0, 0],
   :field_externs=>[false, false, false, false]},
 :next=>157,
 :type=>:clustered,
 :key=>[{:name=>"i", :type=>"INT", :value=>0, :extern=>nil}],
 :transaction_id=>"0000000f4745",
 :roll_pointer=>
  {:is_insert=>true, :rseg_id=>8, :undo_log=>{:page=>312, :offset=>272}},
 :row=>[{:name=>"s", :type=>"CHAR(10)", :value=>"A", :extern=>nil}]}

这应该与上面详细说明的完全一致,因为为了准确起见,我们已经从这个例子中复制了大部分信息,注意以下几个方面:

  • 格式为compact表示该记录是Barracuda格式表中的新的紧凑格式,与Antelope表中的冗余格式相反。
  • 输出列中的key是索引的键字段数组,而row是非键字段数组。
  • transaction_id和roll_pointer字段是每个记录中包含的MVCC的内部字段。因为这是要给集群键(主键)。
  • header总的下一个字段是一个相对offset,必须将其添加到当前记录的offset中,才能计算出下一个记录的实际offset。为了方便期间,这个计算offset被包括在散列next中。
递归一个索引

使用index-recurse模式可以得到一个很好的简单的递归输出,但是由于这任然是一个单索引,输出将非常短:

$ innodb_space -f t_btree.ibd -r ./simple_t_btree_describer.rb -d SimpleTBTreeDescriber -p 3 index-recurse
ROOT NODE #3: 3 records, 96 bytes
  RECORD: (i=0) -> (s=A)
  RECORD: (i=1) -> (s=B)
  RECORD: (i=2) -> (s=C)

构造一个多级索引树

InnoDB中的多级索引树是这样的:

在这里插入图片描述
在这里插入图片描述

如前所述,每个级别上的所有页都是双向链接,并且在每个页中,记录都是安升序单向链接的,非叶子页包含的指针包含子页号,而不是非KEY行数据。 在对innodb_ruby的快速介绍中,如果我们使用创建了100万行的更简单的表模式,树结构看起来会更有趣一些:

$ innodb_space -f t.ibd -r ./simple_t_describer.rb -d SimpleTDescriber -p 3 index-recurse

ROOT NODE #3: 2 records, 26 bytes
  NODE POINTER RECORD >= (i=252) -> #36
  INTERNAL NODE #36: 1117 records, 14521 bytes
    NODE POINTER RECORD >= (i=252) -> #4
    LEAF NODE #4: 446 records, 9812 bytes
      RECORD: (i=1) -> ()
      RECORD: (i=2) -> ()
      RECORD: (i=3) -> ()
      RECORD: (i=4) -> ()

<many lines omitted>

    NODE POINTER RECORD >= (i=447) -> #1676
    LEAF NODE #1676: 444 records, 9768 bytes
      RECORD: (i=447) -> ()
      RECORD: (i=448) -> ()
      RECORD: (i=449) -> ()
      RECORD: (i=450) -> ()

<many lines omitted>

    NODE POINTER RECORD >= (i=891) -> #771
    LEAF NODE #771: 512 records, 11264 bytes
      RECORD: (i=891) -> ()
      RECORD: (i=892) -> ()
      RECORD: (i=893) -> ()
      RECORD: (i=894) -> ()

虽然KEY数组表示的是最小键,而不是确切的键,但是当child_page_number取代它时,没有row出现。

root页面有一点特殊

由于根页面在第一次创建的时候分配,并且该页号存储在数据字典中,因此根用于不能重新定位或者删除,根页面填满之后,需要对其进行分隔,形成一个由根页面和两个叶子页面组成的小树。 但是,根页面本身实际上不能被分隔,因此它不能被重新定位,取而代之的是,分配一个新的空页,根中的记录被移动到那里,根是被提升到的一个级别,并且新页被分成两个,根页面不需要再次分隔,知道它的下一层有了自购多余的页面,使得页面中充满了子页面的指针。称为节点指针。这在实践总通常意味着几百上千个。

B+树层次的增加和树的深度

做为B+树索引效率的一个例子,假设完美的记录打包,每一页都满了,这在实践中永远不会发生,但是在讨论中很有用。对于上面示例中的简单表,InnoDB中的B+树索引将能够为每个叶存储468条记录,或者为每个非叶子存储1203条记录。在给定树的高度的前提下,索引树可以为如下值:

Height

Non-leaf pages

Leaf pages

Rows

Size in bytes

1

0

1

468

16.0 KiB

2

1

1203

> 563 thousand

18.8 MiB

3

1204

1447209

> 677 million

22.1 GiB

4

1448413

1740992427

> 814 billion

25.9 TiB

可以想象,大多数具有合理主键定义的表有2-3级,有些表达到了4级,但是,使用过大的主键会导致B+树的效率大大降低,因为主键值必须存储在非叶子页中,这将大大增非叶子页中的记录的大小。这意味着每个非叶子页能够容量的记录要小得多,从而导致整个结构的效率低下。

下一章介绍

接下来,我们将看看索引页面中的页面目录结构,这已经提到了很多次,然后看看如何在InnoDB中进行高效检索。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-08-24 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • B+树的一些术语:根、叶子和层
  • 叶子页和非叶子页
  • 同一级别的页
  • 单页表详情
    • 创建并填充表
      • 验证空间文件的基本机构
        • 设置record describer
          • 查看记录内容
            • 递归一个索引
            • 构造一个多级索引树
            • root页面有一点特殊
            • B+树层次的增加和树的深度
            • 下一章介绍
            相关产品与服务
            云数据库 SQL Server
            腾讯云数据库 SQL Server (TencentDB for SQL Server)是业界最常用的商用数据库之一,对基于 Windows 架构的应用程序具有完美的支持。TencentDB for SQL Server 拥有微软正版授权,可持续为用户提供最新的功能,避免未授权使用软件的风险。具有即开即用、稳定可靠、安全运行、弹性扩缩等特点。
            领券
            问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档