B树和B+树详解及面试的回答
背景
由于面试被这个问题拷打过好几次、最开始理解的错误诞生了这篇文章
前提
概念：
- 叶子节点：叶子节点是没有子节点的节点，它们位于树的最低层。
- 非叶子节点：非叶子节点（也称为内部节点）是指至少有一个子节点的节点，包括根节点和其他非叶子节点。
混淆、模糊
最开始学的时候很容易跟二叉树混淆，实际上他们差距还是挺大的：
- 二叉树每个节点的元素只有一个，B树和B+树每个节点的元素是根据其分支来决定的
- 二叉树更适用于内存存储和使用，如果用磁盘进行构建和存储会增加磁盘 IO 的次数
- B树和 B+树的设计就是为了减少磁盘 IO 的操作，它构建的树阶数相对较少
B+树的构建
B+树的叶节点包含所有元素，从小到大链接起来（Head指向的最后一层节点叫做叶节点）
- 非叶节点它的目的是为了更好以 Log 级别速度查找到叶子节点的数据（而否通过链表进行顺序查找），通常是通过存储索引值来进行查找的（比如主键索引）
- 叶子节点存储具体的行数据，并使用双向链表链接起来，支持遍历
B树的构建
由于B树没有通过链表链接所有的数据，导致其进行范围查找和顺序查找时只能通过中序遍历并根据范围或顺序进行来回穿梭查找，此时会增加磁盘IO的操作时间，从而耗时
通俗点来说：查询单个数据都差不多，但涉及到多个数据的查找只能根据范围或顺序一个一个的进行查找
每个节点的元素有多个，所以数据都以空格隔开
B树和B+树的特性
作为了解的内容
B树的特性
B树是一种平衡的多叉树，通常我们说m阶的B树，它必须满足如下条件：
- 每个节点最多只有m个子节点。
- 每个非叶子节点（除了根）具有至少⌈ m/2⌉子节点。
- 如果根不是叶节点，则根至少有两个子节点。
- 具有k个子节点的非叶节点包含k -1个键。
- 所有叶子都出现在同一水平，没有任何信息（高度一致）。
B+树的特性
- 有m个子树的中间节点包含有m个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引；
- 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (而B 树的叶子节点并没有包括全部需要查找的信息)；
- 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B 树的非终节点也包含需要查找的有效信息)；
Mysql是如何结合B+树进行存储、读取、查询数据的
InnoDB 引擎使用的是B+树的结构进行索引的存储，那么它是如何进行存储的呢？
数据库中的数据以行为记录进行存储，但读取却并非以行为记录读取，因为这样会导致多次 I/O 操作，效率低效。
因此，InnoDB 的数据是按「数据页」为单位来读写的，数据库的 I/O 操作的最小单位是页，一个数据页对应一个文件（该文件里有很多条行记录），**InnoDB 数据页的默认大小是 16KB，**Mysql 一次最少从磁盘中读取 16K 的内容到内存中。
这里不过多阐述数据页的内容，具体可看小林coding：
https://xiaolincoding.com/mysql/index/page.html
很显然：数据页相当于B+树的叶子节点，并通过文件中的两个指针（指向上一个数据和下一个数据）来实现双向链表的功能
那非叶子节点呢？ 存储导航到叶子节点的指针
那你存储什么能快速导航呢？ 对行记录中的唯一值（可能是主键或其他）进行分组，存储最大的记录，这样查找的时候就可以根据二分查找快速定位到要查找的数据在哪个节点，从而减少 I/O 的次数
比如：以下图例：
比如我们要查找数据 5，由于索引中存储的最大值记录也是从小到大排序的：
- 在根节点的地方通过二分查找（查找到第一个大于或等于该记录的位置）定位到文件C
- 非叶子节点也是类似
- 遍历所有叶子节点，查找数据为 5 的行记录
如果要查找的数据大于分组后最大值的记录呢？ 那二分查找就会溢出下标（找不到）
最容易理解错的地方
最开始看完B+树的视频后我一直以来的困惑是B+树的这个特性：
- 有m个子树的中间节点包含有m个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引
如果真的按照这个特性来说的话，拿一个三阶B+树来说，Mysql 每个节点存储的数据只能有三个元素，那如果数据几百万条，就会使树的高度到达一定的层级并且会增加 I/O 的读取次数。
结果：很显然，Mysql 并非采用此特性，或者说：它以文件为元素，每个节点都对应一个磁盘文件，它是以磁盘进行存储并使用一定的策略保证B+树节点之间相互的联系（16KB）
那么：如果是 B 树的话，一定会使树的高度变大，因为每个节点存放不了多少条行数据，反观 B+ 树因为非叶子节点只存储分组后的某个索引和指针，节省了这一部分空间就可以让树的高度不那么高从而减少磁盘读取的 I /O
B+树一般有几层？能容纳多少数据量？
https://blog.csdn.net/qq_37102984/article/details/124296196?spm=1001.2014.3001.5506
八股文回答
如果面试被问到B+树相对于B树的好处，就很好回答了：
- 由于非叶子节点存储索引，以便快速导航到叶子节点，而叶子节点存储具体的数据，并且可以以双向链表的形式进行遍历，就可以更好的进行顺序查找、范围查找
- Mysql 使用 B+ 树对于磁盘的存储是以每页为单位的，一个页的大小默认是16KB，如果使用B树，那么非叶子节点和叶子节点都会存储具体的行数据（最多十六条），数据变多，树的高度也会变大，从而增加磁盘 I/O 的读取次数，而如果使用 B+ 树在非叶子节点上不存储具体的行数据，只存储分组后的某个索引会节省空间并减少树的高度
参考
参考链接：
博客：
https://blog.csdn.net/it_lihongmin/article/details/114653909
https://blog.csdn.net/qq_56892136/article/details/125508176
Innodb：Innodb存储引擎
图例：
https://www.cs.usfca.edu/~galles/visualization/BTree.html
https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
最后
此文章根据自己的理解和网上的教程进行总结而来，Mysql 使用B+树存储和查询那块如果有误，还请提出来，谢谢大家支持
