目录一、索引页与数据行的紧密关联一数据页的双向链表结构二记录行的单向链表结构二、未创建索引情况一无索引下的单页查找过程以主键为搜索条件以非主键列为搜索条件二无索引下的多页查找过程三、InnoDB中的B 树索引方案初体会一前置说明行格式示意图页内格式示意图二目录项记录与用户记录的区别及其存储目录项放到数据页查找主键为20的记录三分配新目录项记录页更新后的数据页结构查找主键值为20的记录的步骤确定目录项记录页通过目录项记录页确定用户记录所在的页在用户记录页中定位具体记录四多级目录项记录页的介绍高级目录页说明高级目录页页33页30目录项记录页页32目录项记录页查找主键值为20的记录的步骤更新后的过程四、InnoDB中的B 树索引方案确立一B树的数据页结构二B树的层次结构三B树的查找效率五、总结参考文献、书籍及链接干货分享感谢您的阅读在现代数据库系统中如何高效地管理和查找海量数据是一个至关重要的问题。InnoDB作为MySQL的存储引擎通过引入B树这种数据结构解决了这一挑战。B树不仅在索引性能方面表现优异还在数据存储和检索上提供了极高的效率。我们探讨下B树在InnoDB中的实现和应用更好地理解其工作原理和优势。一、索引页与数据行的紧密关联在解读InnoDB数据库索引页与数据行的紧密关联-CSDN博客中我们已经强调过在 InnoDB 中数据页通过双向链表连接每个数据页内的记录行按照主键值从小到大的顺序组成单向链表并且每个数据页都有一个页目录用于快速定位记录。查找记录时先在页目录中使用二分法定位到特定槽再在该槽对应的记录组中顺序遍历找到目标记录。通过这种设计InnoDB 能够高效地管理和查找数据确保数据库系统的高性能和可靠性。一数据页的双向链表结构每个数据页被组织成一个双向链表这意味着每个数据页都有指向前一个页和后一个页的指针File Header 记录了页的基础信息和链表指针。通过这种双向链表结构InnoDB 可以方便地进行数据页的插入、删除和遍历操作。这种设计保证了数据页之间的高效连接和管理。二记录行的单向链表结构具体可见数据库记录行在页内查询探索分析_检查代码中循环依赖-CSDN博客在每个数据页中记录行按照主键值从小到大的顺序组织成一个单向链表。这种有序的结构使得在数据页内查找记录变得更加高效。每条记录不仅存储了自身的数据还包含指向下一条记录的指针这样可以顺序遍历记录。每个数据页都有一个页目录页目录可以看作是数据页内的索引结构。页目录将记录分成多个组每个组在页目录中都有一个槽。通过页目录InnoDB 可以快速定位到特定记录所在的组从而减少遍历记录的时间。当需要通过主键查找某条记录时InnoDB 会先在页目录中使用二分法快速定位到对应的槽。页目录中的槽指向该槽对应的记录组接着在该组中遍历记录直到找到目标记录。这种查找过程结合了二分查找和顺序遍历的优点既高效又精确。二、未创建索引情况在数据库中当没有针对特定列建立索引时查询过程通常会面临效率低下的问题。特别是对于非主键列的精确匹配查询数据库引擎无法利用索引结构从而导致需要全表扫描来寻找符合条件的记录。一无索引下的单页查找过程在数据库中当所有记录都能够存放在一个数据页中时查找记录的过程可以根据查询条件的不同分为以下两种情况以主键为搜索条件对于主键列的精确匹配查询页目录查找数据页通常会维护一个页目录用于存储每条记录的偏移位置。由于页目录是按照主键排序的因此可以使用二分查找法快速定位到对应的记录槽。记录遍历找到对应槽后只需遍历该槽中的记录即可快速找到符合条件的记录。这种方法由于利用了页目录的有序性因此查找效率较高。这部分其实就是我们上文中讲到的理想情况但在开发过程中我们不可能每次都是直接查主键id的情况。以非主键列为搜索条件对于非主键列的精确匹配查询全页扫描由于非主键列没有对应的页目录也没有任何排序信息无法使用二分查找等高效查找算法。此时数据库需要从数据页的最小记录开始逐条遍历每条记录。逐条比较在遍历过程中逐条对比记录是否符合搜索条件。如果记录数较多这种方法的查找效率将会非常低。显然对于非主键列的查找由于缺乏索引的支持只能进行全页扫描这在数据量较大时性能会变得极为低下。二无索引下的多页查找过程在大部分实际应用中表中的记录数量非常庞大往往需要多个数据页来存储这些记录。当在多页中查找记录时查找过程通常可以分为两个步骤定位到记录所在的页。从所在的页中查找相应的记录。在没有索引的情况下无论是根据主键列还是其他列的值进行查找由于无法快速定位到记录所在的页只能沿着数据页的双向链表逐页查找。这意味着遍历页链表从第一个数据页开始沿着双向链表依次访问每一个数据页。逐页查找在每个数据页中使用前面介绍的单页查找方式来查找指定的记录。由于需要遍历所有数据页并在每个页中逐条比较记录这种方式的效率非常低。三、InnoDB中的B 树索引方案初体会一前置说明为了更好地理解 InnoDB 中 B 树索引的工作机制我们从创建一个示例表index_demo开始并通过详细的示意图展示记录在页中的存储结构及索引的作用。CREATE TABLE index_demo ( c1 INT, c2 INT, c3 CHAR(1), PRIMARY KEY (c1) ) ROW_FORMAT Compact;这个表中有两个 INT 类型的列c1和c2一个 CHAR(1) 类型的列c3并且c1列为主键。表的行格式为 Compact。行格式示意图为了更好地展示记录在页中的存储简化index_demo表的行格式示意图每条记录由以下部分组成背景解析MYSQL行头信息数据详细和探究InnoDB Compact行格式背后record_type记录头信息的一项属性表示记录的类型0 表示普通记录1 表示目录项记录2 表示最小记录3 表示最大记录next_record记录头信息的一项属性表示下一条记录地址相对于本记录的地址偏移量。各个列的值记录index_demo表中的三个列c1、c2和c3的值。其他信息除了上述三种信息以外的所有信息包括其他隐藏列的值以及记录的额外信息。为了节省篇幅我们省略记录的其他信息部分并将记录竖着展示页内格式示意图把一些记录放到页里边的示意图就是二目录项记录与用户记录的区别及其存储在 InnoDB 中为了灵活管理 B 树索引的目录项设计者们选择了复用存储用户记录的数据页来存储目录项记录。这种设计使得 InnoDB 能够高效地管理和查询数据。我们来详细分析并讲解这一机制。目录项放到数据页有效地利用已有的数据结构和存储机制通过记录头信息中的record_type属性InnoDB 可以轻松区分目录项记录和用户记录。record_type值为1表示目录项记录值为0表示普通用户记录。目录项记录仅包含主键值和页号这使得它们非常简洁高效。而普通用户记录则包含用户定义的多个列。min_rec_mask属性帮助 InnoDB 快速定位页中主键值最小的目录项记录优化了索引的管理和查询性能。在存储目录项记录的页中主键值最小的目录项记录的min_rec_mask值为1其他记录的min_rec_mask值为0。查找主键为20的记录现在以查找主键为20的记录为例根据某个主键值去查找记录的步骤就可以大致拆分成下面两步先到存储目录项记录的页也就是页30中通过二分法快速定位到对应目录项因为12 20 209所以定位到对应的记录所在的页就是页9。再到存储用户记录的页9中根据二分法快速定位到主键值为20的用户记录。三分配新目录项记录页尽管目录项记录只存储主键值和对应的页号相比于用户记录所需的存储空间要小得多但由于每个数据页只有16KB的大小能够存放的目录项记录数量也是有限的。如果表中的数据非常多以至于单个数据页无法存放所有的目录项记录那么就需要分配更多的目录项记录页。假设一个存储目录项记录的页最多只能存放4条目录项记录请注意这只是个假设实际情况可以存放更多。当需要插入新的目录项记录时比如主键值为320的记录就会出现需要分配新目录项记录页的情况。插入一条主键值为320的用户记录后我们需要新增两个数据页页31用于存储新的用户记录。页32用于存储新的目录项记录因为原先存储目录项记录的页30已经满了假设只能存储4条目录项记录。更新后的数据页结构页30存储目录项记录主键值范围为 [1, 320)。页32存储目录项记录主键值范围为 [320, ∞)。查找主键值为20的记录的步骤现在因为存储目录项记录的页不止一个所以如果我们想根据主键值查找一条用户记录大致需要三个步骤。以查找主键值为20的记录为例确定目录项记录页现在的存储目录项记录的页有两个页30和页32。页30存储的目录项的主键值范围是 [1, 320)页32存储的目录项的主键值范围是不小于320。因此主键值为20的记录对应的目录项记录在页30中。通过目录项记录页确定用户记录所在的页在页30中通过二分法快速定位到主键值为20的目录项记录从而确定该用户记录存储在页9中。在用户记录页中定位具体记录在页9中通过二分法快速定位到主键值为20的用户记录。四多级目录项记录页的介绍在查询步骤的第1步中我们需要定位存储目录项记录的页。然而这些页在存储空间中可能不连续排列。如果表中的数据量非常大会产生许多存储目录项记录的页。那我们怎么根据主键值快速定位一个存储目录项记录的页呢为了解决这个问题我们可以为这些存储目录项记录的页生成一个更高级的目录形成多级目录结构。大目录中嵌套小目录小目录中存储实际的数据。现在各个页的示意图如下高级目录页说明高级目录页页33页33存储更高级的目录项记录用于指向存储目录项记录的页例如页30和页32。页33包含两个目录项记录目录项记录1指向页30范围为[1, 320)目录项记录2指向页32范围为[320, ∞)页30目录项记录页页30存储具体的目录项记录指向用户记录页。目录项记录指向主键值范围在[1, 320)内的用户记录页。页32目录项记录页页32存储具体的目录项记录指向用户记录页。目录项记录指向主键值范围在[320, ∞)内的用户记录页。查找主键值为20的记录的步骤更新后的过程确定高级目录页首先根据主键值在高级目录页页33中进行查找。由于主键值20在范围[1, 320)内所以对应的目录项记录在页30中。确定具体的目录项记录页在页30中通过二分法快速定位到主键值为20的目录项记录从而确定用户记录存储在页9中。在用户记录页中定位具体记录在页9中通过二分法快速定位到主键值为20的用户记录。这里注意我们之前的假设假设一个存储目录项记录的页最多只能存放4条目录项记录请注意这只是个假设实际情况可以存放更多四、InnoDB中的B 树索引方案确立在介绍B树之前我们已经看到了如何通过多级目录结构管理和查找数据。这种结构就像一棵倒过来的树上头是树根下头是树叶。其实这是一种组织数据的形式或者说是一种数据结构它的名称是B树。一B树的数据页结构不论是存放用户记录的数据页还是存放目录项记录的数据页我们都把它们存放到B树这个数据结构中所以我们也称这些数据页为节点。从图中可以看出来我们的实际用户记录都存放在B树的最底层的节点上这些节点也被称为叶子节点或叶节点其余用来存放目录项的节点称为非叶子节点或者内节点其中B树最上面的那个节点也称为根节点。二B树的层次结构设计InnoDB的大佬们为了讨论方便规定最下面的那层也就是存放我们用户记录的那层为第0层之后依次往上加。为了简化我们之前做了一个非常极端的假设存放用户记录的页最多存放3条记录存放目录项记录的页最多存放4条记录。其实在真实环境中一个页存放的记录数量是非常大的。假设所有存放用户记录的叶子节点代表的数据页可以存放100条用户记录所有存放目录项记录的内节点代表的数据页可以存放1000条目录项记录那么如果B树只有1层也就是只有1个用于存放用户记录的节点最多能存放100条记录。如果B树有2层最多能存放1000×100100,000条记录。如果B树有3层最多能存放1000×1000×100100,000,000条记录。如果B树有4层最多能存放1000×1000×1000×100100,000,000,000条记录。哇咔咔这么多的记录但实际上可推演得出结论当单行数据大小为S字节树高为H时一个bigint类型的主键B树索引中可以存放的数量行数N等于按公式计算当树高为4时可以存放200百多亿行数据。这样的数据容量可以满足绝大部分应用的需求因此我们可以说在绝大部分应用中B树高度为3或4就可以满足数据存储的需求。B树这种高扇出低树高的特征也大大的提高了主键查询性能。具体推导可见InnoDB存储引擎B树的树高推导_b树一般多少层-CSDN博客三B树的查找效率你的表里能存放100,000,000,000条记录么所以一般情况下我们用到的B树都不会超过4层那我们通过主键值去查找某条记录最多只需要做4个页面内的查找查找3个目录项页和一个用户记录页又因为在每个页面内有所谓的Page Directory页目录所以在页面内也可以通过二分法实现快速定位记录这不是很牛么通过引入B树InnoDB能够高效地管理和查找大量数据。B树的结构保证了即使在处理大规模数据时查找过程仍然高效。每一层增加的节点数使得数据的管理和查找变得更加迅速和可靠。B树是数据库系统中广泛使用的索引结构通过这种结构InnoDB能够在庞大的数据集中快速、准确地找到所需的记录为数据库性能提供了有力的保障。五、总结综上所述B树作为InnoDB的核心索引结构通过多级目录和高效的节点管理实现了快速的数据查找和管理。其高扇出、低树高的特性使得即使在处理大规模数据时查找过程仍然保持高效通常不超过四层的树结构足以满足大部分应用需求。通过B树InnoDB在庞大的数据集中能够快速、准确地找到所需记录显著提高了数据库的性能和可靠性。其页目录、双向链表和单向链表等设计进一步优化了数据存储和查找过程使得数据库系统在面对复杂查询时依然能够保持高效运作。B树不仅在数据组织和存储方面展现了强大的能力更通过实际应用证明了其在数据库管理系统中的不可替代性。总之B树的引入和使用使得InnoDB能够在现代数据库系统中脱颖而出成为高性能、高可靠性的代名词。参考文献、书籍及链接《MySQL技术内幕InnoDB存储引擎》第2版MySQL技术内幕 (豆瓣)《MySQL 是怎样运行的从根儿上理解 MySQL》《Inside InnoDB: The InnoDB Storage Engine》MySQL :: MySQL 8.0 Reference Manual :: 15 The InnoDB Storage Engine《InnoDB: The Ultimate Guide》https://www.percona.com/blog/2018/06/05/innodb-the-ultimate-guide/《InnoDB Storage Engine Internals》https://mariadb.com/kb/en/innodb-storage-engine-internals/InnoDB的数据页结构 深入InnoDB核心：揭秘B+树在数据库索引中的高效应用
目录一、索引页与数据行的紧密关联一数据页的双向链表结构二记录行的单向链表结构二、未创建索引情况一无索引下的单页查找过程以主键为搜索条件以非主键列为搜索条件二无索引下的多页查找过程三、InnoDB中的B 树索引方案初体会一前置说明行格式示意图页内格式示意图二目录项记录与用户记录的区别及其存储目录项放到数据页查找主键为20的记录三分配新目录项记录页更新后的数据页结构查找主键值为20的记录的步骤确定目录项记录页通过目录项记录页确定用户记录所在的页在用户记录页中定位具体记录四多级目录项记录页的介绍高级目录页说明高级目录页页33页30目录项记录页页32目录项记录页查找主键值为20的记录的步骤更新后的过程四、InnoDB中的B 树索引方案确立一B树的数据页结构二B树的层次结构三B树的查找效率五、总结参考文献、书籍及链接干货分享感谢您的阅读在现代数据库系统中如何高效地管理和查找海量数据是一个至关重要的问题。InnoDB作为MySQL的存储引擎通过引入B树这种数据结构解决了这一挑战。B树不仅在索引性能方面表现优异还在数据存储和检索上提供了极高的效率。我们探讨下B树在InnoDB中的实现和应用更好地理解其工作原理和优势。一、索引页与数据行的紧密关联在解读InnoDB数据库索引页与数据行的紧密关联-CSDN博客中我们已经强调过在 InnoDB 中数据页通过双向链表连接每个数据页内的记录行按照主键值从小到大的顺序组成单向链表并且每个数据页都有一个页目录用于快速定位记录。查找记录时先在页目录中使用二分法定位到特定槽再在该槽对应的记录组中顺序遍历找到目标记录。通过这种设计InnoDB 能够高效地管理和查找数据确保数据库系统的高性能和可靠性。一数据页的双向链表结构每个数据页被组织成一个双向链表这意味着每个数据页都有指向前一个页和后一个页的指针File Header 记录了页的基础信息和链表指针。通过这种双向链表结构InnoDB 可以方便地进行数据页的插入、删除和遍历操作。这种设计保证了数据页之间的高效连接和管理。二记录行的单向链表结构具体可见数据库记录行在页内查询探索分析_检查代码中循环依赖-CSDN博客在每个数据页中记录行按照主键值从小到大的顺序组织成一个单向链表。这种有序的结构使得在数据页内查找记录变得更加高效。每条记录不仅存储了自身的数据还包含指向下一条记录的指针这样可以顺序遍历记录。每个数据页都有一个页目录页目录可以看作是数据页内的索引结构。页目录将记录分成多个组每个组在页目录中都有一个槽。通过页目录InnoDB 可以快速定位到特定记录所在的组从而减少遍历记录的时间。当需要通过主键查找某条记录时InnoDB 会先在页目录中使用二分法快速定位到对应的槽。页目录中的槽指向该槽对应的记录组接着在该组中遍历记录直到找到目标记录。这种查找过程结合了二分查找和顺序遍历的优点既高效又精确。二、未创建索引情况在数据库中当没有针对特定列建立索引时查询过程通常会面临效率低下的问题。特别是对于非主键列的精确匹配查询数据库引擎无法利用索引结构从而导致需要全表扫描来寻找符合条件的记录。一无索引下的单页查找过程在数据库中当所有记录都能够存放在一个数据页中时查找记录的过程可以根据查询条件的不同分为以下两种情况以主键为搜索条件对于主键列的精确匹配查询页目录查找数据页通常会维护一个页目录用于存储每条记录的偏移位置。由于页目录是按照主键排序的因此可以使用二分查找法快速定位到对应的记录槽。记录遍历找到对应槽后只需遍历该槽中的记录即可快速找到符合条件的记录。这种方法由于利用了页目录的有序性因此查找效率较高。这部分其实就是我们上文中讲到的理想情况但在开发过程中我们不可能每次都是直接查主键id的情况。以非主键列为搜索条件对于非主键列的精确匹配查询全页扫描由于非主键列没有对应的页目录也没有任何排序信息无法使用二分查找等高效查找算法。此时数据库需要从数据页的最小记录开始逐条遍历每条记录。逐条比较在遍历过程中逐条对比记录是否符合搜索条件。如果记录数较多这种方法的查找效率将会非常低。显然对于非主键列的查找由于缺乏索引的支持只能进行全页扫描这在数据量较大时性能会变得极为低下。二无索引下的多页查找过程在大部分实际应用中表中的记录数量非常庞大往往需要多个数据页来存储这些记录。当在多页中查找记录时查找过程通常可以分为两个步骤定位到记录所在的页。从所在的页中查找相应的记录。在没有索引的情况下无论是根据主键列还是其他列的值进行查找由于无法快速定位到记录所在的页只能沿着数据页的双向链表逐页查找。这意味着遍历页链表从第一个数据页开始沿着双向链表依次访问每一个数据页。逐页查找在每个数据页中使用前面介绍的单页查找方式来查找指定的记录。由于需要遍历所有数据页并在每个页中逐条比较记录这种方式的效率非常低。三、InnoDB中的B 树索引方案初体会一前置说明为了更好地理解 InnoDB 中 B 树索引的工作机制我们从创建一个示例表index_demo开始并通过详细的示意图展示记录在页中的存储结构及索引的作用。CREATE TABLE index_demo ( c1 INT, c2 INT, c3 CHAR(1), PRIMARY KEY (c1) ) ROW_FORMAT Compact;这个表中有两个 INT 类型的列c1和c2一个 CHAR(1) 类型的列c3并且c1列为主键。表的行格式为 Compact。行格式示意图为了更好地展示记录在页中的存储简化index_demo表的行格式示意图每条记录由以下部分组成背景解析MYSQL行头信息数据详细和探究InnoDB Compact行格式背后record_type记录头信息的一项属性表示记录的类型0 表示普通记录1 表示目录项记录2 表示最小记录3 表示最大记录next_record记录头信息的一项属性表示下一条记录地址相对于本记录的地址偏移量。各个列的值记录index_demo表中的三个列c1、c2和c3的值。其他信息除了上述三种信息以外的所有信息包括其他隐藏列的值以及记录的额外信息。为了节省篇幅我们省略记录的其他信息部分并将记录竖着展示页内格式示意图把一些记录放到页里边的示意图就是二目录项记录与用户记录的区别及其存储在 InnoDB 中为了灵活管理 B 树索引的目录项设计者们选择了复用存储用户记录的数据页来存储目录项记录。这种设计使得 InnoDB 能够高效地管理和查询数据。我们来详细分析并讲解这一机制。目录项放到数据页有效地利用已有的数据结构和存储机制通过记录头信息中的record_type属性InnoDB 可以轻松区分目录项记录和用户记录。record_type值为1表示目录项记录值为0表示普通用户记录。目录项记录仅包含主键值和页号这使得它们非常简洁高效。而普通用户记录则包含用户定义的多个列。min_rec_mask属性帮助 InnoDB 快速定位页中主键值最小的目录项记录优化了索引的管理和查询性能。在存储目录项记录的页中主键值最小的目录项记录的min_rec_mask值为1其他记录的min_rec_mask值为0。查找主键为20的记录现在以查找主键为20的记录为例根据某个主键值去查找记录的步骤就可以大致拆分成下面两步先到存储目录项记录的页也就是页30中通过二分法快速定位到对应目录项因为12 20 209所以定位到对应的记录所在的页就是页9。再到存储用户记录的页9中根据二分法快速定位到主键值为20的用户记录。三分配新目录项记录页尽管目录项记录只存储主键值和对应的页号相比于用户记录所需的存储空间要小得多但由于每个数据页只有16KB的大小能够存放的目录项记录数量也是有限的。如果表中的数据非常多以至于单个数据页无法存放所有的目录项记录那么就需要分配更多的目录项记录页。假设一个存储目录项记录的页最多只能存放4条目录项记录请注意这只是个假设实际情况可以存放更多。当需要插入新的目录项记录时比如主键值为320的记录就会出现需要分配新目录项记录页的情况。插入一条主键值为320的用户记录后我们需要新增两个数据页页31用于存储新的用户记录。页32用于存储新的目录项记录因为原先存储目录项记录的页30已经满了假设只能存储4条目录项记录。更新后的数据页结构页30存储目录项记录主键值范围为 [1, 320)。页32存储目录项记录主键值范围为 [320, ∞)。查找主键值为20的记录的步骤现在因为存储目录项记录的页不止一个所以如果我们想根据主键值查找一条用户记录大致需要三个步骤。以查找主键值为20的记录为例确定目录项记录页现在的存储目录项记录的页有两个页30和页32。页30存储的目录项的主键值范围是 [1, 320)页32存储的目录项的主键值范围是不小于320。因此主键值为20的记录对应的目录项记录在页30中。通过目录项记录页确定用户记录所在的页在页30中通过二分法快速定位到主键值为20的目录项记录从而确定该用户记录存储在页9中。在用户记录页中定位具体记录在页9中通过二分法快速定位到主键值为20的用户记录。四多级目录项记录页的介绍在查询步骤的第1步中我们需要定位存储目录项记录的页。然而这些页在存储空间中可能不连续排列。如果表中的数据量非常大会产生许多存储目录项记录的页。那我们怎么根据主键值快速定位一个存储目录项记录的页呢为了解决这个问题我们可以为这些存储目录项记录的页生成一个更高级的目录形成多级目录结构。大目录中嵌套小目录小目录中存储实际的数据。现在各个页的示意图如下高级目录页说明高级目录页页33页33存储更高级的目录项记录用于指向存储目录项记录的页例如页30和页32。页33包含两个目录项记录目录项记录1指向页30范围为[1, 320)目录项记录2指向页32范围为[320, ∞)页30目录项记录页页30存储具体的目录项记录指向用户记录页。目录项记录指向主键值范围在[1, 320)内的用户记录页。页32目录项记录页页32存储具体的目录项记录指向用户记录页。目录项记录指向主键值范围在[320, ∞)内的用户记录页。查找主键值为20的记录的步骤更新后的过程确定高级目录页首先根据主键值在高级目录页页33中进行查找。由于主键值20在范围[1, 320)内所以对应的目录项记录在页30中。确定具体的目录项记录页在页30中通过二分法快速定位到主键值为20的目录项记录从而确定用户记录存储在页9中。在用户记录页中定位具体记录在页9中通过二分法快速定位到主键值为20的用户记录。这里注意我们之前的假设假设一个存储目录项记录的页最多只能存放4条目录项记录请注意这只是个假设实际情况可以存放更多四、InnoDB中的B 树索引方案确立在介绍B树之前我们已经看到了如何通过多级目录结构管理和查找数据。这种结构就像一棵倒过来的树上头是树根下头是树叶。其实这是一种组织数据的形式或者说是一种数据结构它的名称是B树。一B树的数据页结构不论是存放用户记录的数据页还是存放目录项记录的数据页我们都把它们存放到B树这个数据结构中所以我们也称这些数据页为节点。从图中可以看出来我们的实际用户记录都存放在B树的最底层的节点上这些节点也被称为叶子节点或叶节点其余用来存放目录项的节点称为非叶子节点或者内节点其中B树最上面的那个节点也称为根节点。二B树的层次结构设计InnoDB的大佬们为了讨论方便规定最下面的那层也就是存放我们用户记录的那层为第0层之后依次往上加。为了简化我们之前做了一个非常极端的假设存放用户记录的页最多存放3条记录存放目录项记录的页最多存放4条记录。其实在真实环境中一个页存放的记录数量是非常大的。假设所有存放用户记录的叶子节点代表的数据页可以存放100条用户记录所有存放目录项记录的内节点代表的数据页可以存放1000条目录项记录那么如果B树只有1层也就是只有1个用于存放用户记录的节点最多能存放100条记录。如果B树有2层最多能存放1000×100100,000条记录。如果B树有3层最多能存放1000×1000×100100,000,000条记录。如果B树有4层最多能存放1000×1000×1000×100100,000,000,000条记录。哇咔咔这么多的记录但实际上可推演得出结论当单行数据大小为S字节树高为H时一个bigint类型的主键B树索引中可以存放的数量行数N等于按公式计算当树高为4时可以存放200百多亿行数据。这样的数据容量可以满足绝大部分应用的需求因此我们可以说在绝大部分应用中B树高度为3或4就可以满足数据存储的需求。B树这种高扇出低树高的特征也大大的提高了主键查询性能。具体推导可见InnoDB存储引擎B树的树高推导_b树一般多少层-CSDN博客三B树的查找效率你的表里能存放100,000,000,000条记录么所以一般情况下我们用到的B树都不会超过4层那我们通过主键值去查找某条记录最多只需要做4个页面内的查找查找3个目录项页和一个用户记录页又因为在每个页面内有所谓的Page Directory页目录所以在页面内也可以通过二分法实现快速定位记录这不是很牛么通过引入B树InnoDB能够高效地管理和查找大量数据。B树的结构保证了即使在处理大规模数据时查找过程仍然高效。每一层增加的节点数使得数据的管理和查找变得更加迅速和可靠。B树是数据库系统中广泛使用的索引结构通过这种结构InnoDB能够在庞大的数据集中快速、准确地找到所需的记录为数据库性能提供了有力的保障。五、总结综上所述B树作为InnoDB的核心索引结构通过多级目录和高效的节点管理实现了快速的数据查找和管理。其高扇出、低树高的特性使得即使在处理大规模数据时查找过程仍然保持高效通常不超过四层的树结构足以满足大部分应用需求。通过B树InnoDB在庞大的数据集中能够快速、准确地找到所需记录显著提高了数据库的性能和可靠性。其页目录、双向链表和单向链表等设计进一步优化了数据存储和查找过程使得数据库系统在面对复杂查询时依然能够保持高效运作。B树不仅在数据组织和存储方面展现了强大的能力更通过实际应用证明了其在数据库管理系统中的不可替代性。总之B树的引入和使用使得InnoDB能够在现代数据库系统中脱颖而出成为高性能、高可靠性的代名词。参考文献、书籍及链接《MySQL技术内幕InnoDB存储引擎》第2版MySQL技术内幕 (豆瓣)《MySQL 是怎样运行的从根儿上理解 MySQL》《Inside InnoDB: The InnoDB Storage Engine》MySQL :: MySQL 8.0 Reference Manual :: 15 The InnoDB Storage Engine《InnoDB: The Ultimate Guide》https://www.percona.com/blog/2018/06/05/innodb-the-ultimate-guide/《InnoDB Storage Engine Internals》https://mariadb.com/kb/en/innodb-storage-engine-internals/InnoDB的数据页结构