笔记自 https://www.bilibili.com/video/BV1UC4y1p7zm?from=search&seid=3639400807332749680&spm_id_from=333.337.0.0 [toc]

# 从磁盘说起

如图所示，古早非固态的磁盘通常是通过快速切换磁道和扇区来进行数据的读写。当我们想对磁盘上的数据进行存储时，我们就需要先将数据存到 RAM 中，然后再回到磁盘进行数据的读写。这中间会产生一些延时.

# 索引的好处

所以如果当我们有如下这样一张表的时候 如果我们不做任何索引处理，想要查找一条数据均摊要遍历一遍所有的数据. ※※ 而且，由于这些数据的 索引和数据的字段是同时存在在内存中的 ，所以当检查内存的时候，就算遍历也会花费更多的时间。一种简单的优化方式是：当我只需要遍历 id 时，我们就建立一张只有 id 的索引表，表内有一个数据的指针，这个指针指向各自的数据，这样一来我们遍历 id 时就会稍微少那么一点硬件上的消耗 这就是索引的好处 但是如果索引的层级多起来，那这样做毫无意义，反而会增加硬件上的消耗 而 B + 树的目的就是将索引也拆开存放，不同区间索引在不同的块存储上。所以事实上 B&B + 树本质上就是把索引拆开成一棵树

# B 树的结构

右侧指向的是实际存储的样子
左侧指向的是逻辑存储的样子 事实上 B 树也是二分查找，只是它每层的每个节点上存在不止一个二分方向。如左图所示，小于 K1, 就走 K1 左侧，在 K1,K2 之间，就走中间那个… 而 B 树不过是一堆成文的约束.
1. 每个节点的叶子节点最大大于等于 ceil (m/2) 个孩子节点 2. 根节点至少两个孩子节点. 3. 所有叶子节点必须在同一级别

# B 树的构造过程

需要先指定每个节点最大的索引数 (比如 m=4)
m=4 (可能有误), 就代表每个节点上最多三个索引，当同一个节点插入的索引的数量超过三个时，就会把倒数第二个往上冒一个层级，然后剩下的节点拆成 [2 个，1 个] 这样的两个索引节点。然后重新连接与数据的关系

# 所以什么是 B+Tree

B + 树不会再每个节点上都有对数据的引用，只会在最后一层的叶子节点上对数据有引用，并且最后一层的叶子节点是个链表 (或者数组), B + 树的所有值，都必须出现在最后一层的叶子节点上。如果使用数组的形式存储这些数据，那么在到最后一级进行二分或者遍历的时候，硬件层的消耗就会很低.