[串联] MySQL 存储原理 B+树

本文主要是介绍[串联] MySQL 存储原理 B+树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

InnoDB 是一种兼顾高可靠性和高性能的通用存储引擎，在 MySQL 5.5 之后，InnoDB 是默认的 MySQL 存储引擎。 InnoDB 对每张表在磁盘中的存储以 xxx.ibd 后缀结尾，innoDB 引擎的每张表都会对应这样一个表空间文件，用来存储该表的表结构（frm、sdi）、数据和索引。

存储结构

InnoDB 的逻辑存储结构：表空间、段、区、页、行

InnoDB是以数据页为单位来读写数据的，数据页大小默认是16KB，每次从磁盘最少读取16KB的数据到内存，或者刷新内存中16KB的数据到磁盘

数据页

文件头记录数据页的信息，包括两个指针，一个指向上一个数据页，一个指向下一个数据页

每个数据页中存储了详细的记录数据

记录

• UserRecord中存储了行记录，这些记录会通过单向链表按照主键的顺序有小到大排列
• 单向链表的检索效率比较低，所以数据页中还有一个页目录结构帮助快速查找记录。
• 数据页中的记录被分为若干组，当然，带有删除标识的不会参与分组；每组中的记录也是按照主键从小到大排序，每组中最后一条记录的主键值最大，它的头信息中记录了本组的记录条数（n_owned字段），页目录记录了每组最大最后一条记录的地址偏移量，叫做槽，它相当于指针指向了不同组的最后一条记录。
• 当我们检索数据页中的记录时，由于记录都是按照主键大小排列的，可以使用槽号进行二分法定位某个槽，也就是定位到某一组，然后比较该组的最大记录的主键值，最终定位到某个槽。由于槽都是定位到每组最大的那条记录，所以如果要定位到最小的那条记录，可以通过查找上一个槽的最后一条记录，然后沿着单向链表向后检索

为了减少在某个分组中检索的时间复杂度，InnoDB规定了每个分组的大小

1. 第一个分组只能有一条记录
2. 最后一个分组记录条数在1-8之间
3. 其余分组记录条数在4-8之间

B-树介绍

B-树，也称为B树，是一种平衡的多叉树。

        阶数：一个节点最多有多少个孩子节点。（一般用字母m表示）关键字：节点上的数值就是关键字度：一个节点拥有的子节点的数量。
一颗m阶的b-树：根结点至少有两个子女；每个非根节点所包含的关键字个数 j 满足：⌈m/2⌉ - 1 <= j <= m - 1.(⌈⌉表示向上取整)有k个关键字(关键字按递增次序排列)的非叶结点恰好有k+1个孩子。所有的叶子结点都位于同一层。

B+ 树原理

B+树是B-树的变体，也是一颗多路搜索树

• 每个结点至多有m个子女;
• 非根节点关键值个数范围：m/2 <= k <= m-1
• 相邻叶子节点是通过指针连起来的，并且是关键字大小排序的。

## 区别：
B-树内部节点是保存数据的;而B+树内部节点是不保存数据的，只作索引作用，它的叶子节点才保存数据。
B+树相邻的叶子节点之间是通过链表指针连起来的，B-树却不是。
查找过程中，B-树在找到具体的数值以后就结束，而B+树则需要通过索引找到叶子结点中的数据才结束
B-树中任何一个关键字出现且只出现在一个结点中，而B+树可以出现多次。

1. 插入

   流程：

   1.B+树插入都是在叶子结点进行的，就是插入前，需要先找到要插入的叶子结点。

   2.如果被插入关键字的叶子节点，当前含有的关键字数量是小于阶数m，则直接插入。

   3.如果插入关键字后，叶子节点当前含有的关键字数目等于阶数m，则插，该节点开始分裂为两个新的节点，一个节点包含⌊m/2⌋ 个关键字，另外一个关键字包含⌈m/2⌉个关键值。（⌊m/2⌋表示向下取整，⌈m/2⌉表示向上取整，如⌈3/2⌉=2）。

   4.分裂后，需要将第⌈m/2⌉的关键字上移到父结点。如果这时候父结点中包含的关键字个数小于m，则插入操作完成。

   5.分裂后，需要将⌈m/2⌉的关键字上移到父结点。如果父结点中包含的关键字个数等于m，则继续分裂父结点。

   参考：https://juejin.cn/post/6929833495082565646?searchId=20240301221957FB5B4942920DC0A4744E

2. 查找

   单值查询：查找32

   第一次磁盘 I/O，查找磁盘块1，即根节点（36,43）,因为32小于36，因此访问根节点的左边第一个孩子节点

   第二次磁盘 I/O, 查找磁盘块2，即根节点的第一个孩子节点，获得区间(28,32),遍历即可得32.

   

   范围查询： [32,40]

   第一步先访问根节点，发现区间的左端点32小于36,则访问根节点的第一个左子树(28,32);

   第二步访问节点（28,32），找到32，于是开始遍历链表，把[32,40]区间值找出来，这也是B+树比B-树高效的地方。

3. 删除

• 找到包含关键值的结点，如果关键字个数大于m/2，直接删除即可；
• 找到包含关键值的结点,如果关键字个数大于m/2，并且关键值是当前节点的最大（小）值，并且该关键值存在父子节点中，那么删除该关键字，同时需要相应调整父节点的值。
• 找到包含关键值的结点，如果删除该关键字后，关键字个数小于⌈m/2⌉，并且其兄弟结点有多余的关键字，则从其兄弟结点借用关键字
• 找到包含关键值的结点，如果删除该关键字后，关键字个数小于⌈m/2⌉，并且其兄弟结点没有多余的关键字，则与兄弟结点合并。

常见问题

1. InnoDB一棵B+树可以存放多少行数据？

   约2千万行

   在计算机中，磁盘存储数据最小单元是扇区，一个扇区的大小是512字节。
   文件系统中，最小单位是块，一个块大小就是4k；
   InnoDB存储引擎最小储存单元是页，一页大小就是16k。
   

   • 如果一行记录的数据大小为1k，那么单个叶子节点可以存的记录数 =16k/1k =16.
   • 假设主键ID为bigint类型，长度为8字节，而指针大小在InnoDB源码中设置为6字节，非叶节点的一条记录为8+6=14字节，可存放16k/14B= 1170条
   • 因此，一棵高度为2的B+树，能存放1170 * 16=18720条这样的数据记录。同理一棵高度为3的B+树，能存放1170 *1170 *16 =21902400，也就是说，可以存放两千万左右的记录。B+树高度一般为1-3层，已经满足千万级别的数据存储。

   

2. 为什么索引结构默认使用B+树，而不是hash，二叉树，红黑树，B-树？

   • Hash哈希，只适合等值查询，不适合范围查询。

   • 一般二叉树，可能会特殊化为一个链表，相当于全表扫描。

   • 红黑树，是一种特化的平衡二叉树，MySQL 数据量很大的时候，索引的体积也会很大，内存放不下的而从磁盘读取，树的层次太高的话，读取磁盘的次数就多了。

   • B-Tree，叶子节点和非叶子节点都保存数据，相同的数据量，B+树更爱矮壮，也是就说，相同的数据量，B+树数据结构，查询磁盘的次数会更少。

3. B-树和B+树的区别

   • B-树内部节点是保存数据的;而B+树内部节点是不保存数据的，只作索引作用，它的叶子节点才保存数据。
   • B+树相邻的叶子节点之间是通过链表指针连起来的，B-树却不是。
   • 查找过程中，B-树在找到具体的数值以后就结束，而B+树则需要通过索引找到叶子结点中的数据才结束
   • B-树中任何一个关键字出现且只出现在一个结点中，而B+树同一个键值可在不同层级的节点中重复出现。

4. B+树和红黑树的区别

   • B+树的所有值都存在于叶子节点，并且叶子节点之间通过指针连接，形成一个有序链表。这种结构非常适合范围查询，红黑树虽然在单个元素查找上有优势，但需要进行额外的遍历才能完成范围查询。
   • 由于B+树具有顺序访问的特性，数据库系统可以利用预读优化来提高连续磁盘块的读取性能。而红黑树的结构不容易进行批量的顺序读取操作，因此无法充分利用预读特性。
   • B+树通过将键和数据分离使得节点可以存放更多的键。这样就可以减少树的高度，红黑树作为二叉树在存储大量数据时会占据更多空间，因为每个节点只有两个子节点的指针。

5. 为什么索引使用B+树不使用跳表？

   磁盘I/O效率：B+树特别适合于磁盘存储的优化。它们能够最小化磁盘I/O操作，因为一个节点通常对应一个磁盘块的大小，这样可以减少读取数据时所需的磁盘访问次数。跳表在内存中运行效率较高，但当涉及到磁盘操作时，其性能可能会下降，因为跳表的节点间隔是不规则的，不一定能有效利用磁盘块的空间。

   删除操作：在B+树中，插入和删除操作可以更容易地保持树的平衡，而且不需要重新组织整个数据结构。虽然跳表支持比较简单的插入和删除操作，但在大量的更新操作后可能需要额外的工作来重新平衡。

   存储利用率：B+树的节点通常设计为页大小，以便与磁盘或文件系统页面对齐，从而实现高效的空间利用。而跳表可能会因为其节点大小不一致而在某些情况下导致存储空间利用率不高。

这篇关于[串联] MySQL 存储原理 B+树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---