https://15445.courses.cs.cmu.edu/fall2018/slides/07-trees1.pdf
表索引
表索引是表的列子集的副本，这些列的组织和/或排序使得可以进行快速访问。
但是如果表索引创建过多，会有维护成本（插入删除 要更新索引文件）和额外的存储成本(每建一个索引多一个索引文件）。
b+树的基本概念 这边不过多介绍。
重点讲解下homework2 里的b+树 是怎么分裂和合并的。
https://15445.courses.cs.cmu.edu/fall2018/files/hw2-clean.pdf
image.png
综上需要走4个指针。
image.png
第一题解
image.png
第二题解
先找到18要插的叶子节点，随后发现满了。开始做分裂，前半部分和后半部分断开，后半部分的指针指到19.前半部分的指针指向后半部分。同时为了链接前半部分 和 后半部分，父亲节点需要多一个，以后半部分的第一个为值，插入父节点。
image.png
image.png
第三题解
image.png
借过来之后，需要把父亲节点更新为右边最左元素的值。
image.png
第四题解
首先删掉了31，没有元素可借，触发第一次合并。32到左边那里去，同时删掉父节点的30.
随后父节点没元素了，，再次触发合并，合并用的是下面已经合并的那个节点的最左端的值，同时删除祖父节点26.
image.png
image.png
image.png
第一题解
这道题就是分裂2次，因为父亲节点也满了，按照相同套路再分裂一次。
image.png
image.png
第二题解
image.png
image.png
B+树特性
1. 节点大小
B +树的最佳节点大小取决于磁盘的速度。 想法是通过尽可能多的键/值对来分摊从磁盘读取节点到内存的成本。
磁盘越慢，则构思节点大小越大。
有些负载可能是区域扫描更多，而不是单键查找。
2. 合并的阈值
有些DBMS在半满时并不总是合并。
延迟合并操作可能会减少重组量。
DBMS可能更好地发生下溢，然后定期重建整个树以重新平衡它。
3. 变长的KEY
•指针：存储键作为元组属性的指针（很少使用）。
•可变长度节点：B +树中每个节点的大小可能不同，但需要仔细的内存管理。 这种方法也很少见。
•键映射：嵌入一组指针，指针是映射到节点key+value 列表。 这类似于之前讨论的slotted page。 这是最常用的方法。
image.png
4. 非唯一的KEY
允许KEY重复多次
image.png
只出现一次，VALUE用链表连起来
image.png
5.节点内部的查找
也有3种方法，线性查找。二分查找（PROJECT里我选用这种），预先估计可能的位置，随后线性查找。
B+树的优化
分为前缀压缩，后缀截断，批量插入，指针滑动。
前缀压缩指的是在一个叶子节点上，如果KEY拥有共有前缀，可以提取出来，节约存储空间。
image.png
后缀截断指的是在中间节点，不一定需要全部的数据才能做ROUTE，可能一定的头上的数据量就够了，再多的数据也没有帮助，就可以把没有帮助的部分给截断了。
image.png
image.png
批量插入指的是一个一个插入效率很低，因为需要不断做分裂。高效的做法是，等插入了很多之后，一次性，做一个B+树的重建。
image.png
指针滑动指的是，当我们要切换PAGE的时候，如果需要的PAGE在BUFFER POOL MANGER里已经有了，并且PIN住了，我们可以直接不存那个PAGE ID，而是存指向BUFFER POOL的PAGE的指针。这样就可以从内存里直接拿了。
image.png
网友评论