B+树Search的问题

顺序索引的缺点是：对于查找index和顺序扫描而言，文件越大效率越低。尽管我们可以通过file reorganization来给它优化，但是频繁的这样做是undesirable的。
B+树是其中最好的一种索引，其插入和删除依旧可以保持很高的效率。B+树采用了Balanced Tree的做法，即 每一个从root到leaf的距离都是相等的。我们假定一个数字n，让非根节点和非叶节点的child数量保持在n除以2向下取整到n之间，让root保持在2到n个孩子之间（如果根不是叶节点，则根至少有两个节点），让叶节点的元素个数保持在n - 1到 (n - 1) / 2向下取整之间，让具有k个字节点的非叶节点包含k-1个child。我们就可以看到，尽管（1）B+树的插入和删除相当麻烦。（2）每个节点都可以保持一种half empty，即半空的状态，会浪费空间。，即使这样，它也是最优的，因为无需file reorganization。

B+树的本质是多层索引，但又有别于顺序多层索引。
Database System Concept这本书将B+树按照unique search key（无重复search key）和none unique search key（有重复search key）分别讨论，首先先讨论第一种情况：
假定：B+树的单个node有n-1个search key value，[k1, ... kn-1]，每一个key都被一个指针指向，那么就有n个指针。所以我们可以猜测出此node的结构：[p1->k1, p2->k2, .., pn-1->kn-1, pn]，最后pn指向下一个node。假定1 < i < j < n，那么ki < kj。

一个矛盾的问题是，B+树到底是稠密索引，还是稀疏索引？书上有提到：“If the B+-tree index is used as a dense index (as is usually the case), every search-key value must appear in some leaf node.”，那也就是说，B+树是dense index。书上又说：“The nonleaf nodes of the B+-tree form a multilevel (sparse) index on the leaf nodes.”。说明中间节点又是稀疏索引。综上，我们并不能简单的定义B+树到底是sparse index还是dense index，这样都是以偏概全的。

按照这张图的情况，我们假定一个节点包含了m个指针，m <= n，Pm指针有两种存在的可能，假设其对应的search key是Km，上一个则key是Km-1。（1）当这个Pm是P1的时候，Pm指的子树是所有节点都小于K1的。（2）当Pm不是P1的时候，其指的子树的值要大于等于Km-1。
之前提到，数据库要处理none unique search key的情况。书有提到了两种错误的构想和一种对的构想。
（1）将重复的search key往后延伸，且将条件更改为i<j那么Ki<=Kj。
（2）将重复的search key作为一个bucket，每一个桶内存record pointers。
这两种都是不现实的，第一种会很难写，第二种占内存。
正确的解决办法是规定一个正确的主键ID，将可能重复的key比如Name组合一个复合主键<ID, Name>。

Search

Search比想象的简单，本来以为这种复杂的结构会用递归什么的。
简单来说，假设v是目标key，循环遍历当前节点的元素，寻找比v大的元素的最小值，首先建立一个cursor，此游标是一个B+树节点的指针。
（1）假设没有，那么v本身是最大的，寻找此节点最后一个非空指针，将cursor后移。也就是说比v大的节点在下一层。
（2）假设有，那么那么v不是最大的，所以要找大于等于且最接近于v的ki
（3）假设有等于v的ki，那么，下一层也一样会出现等于v的kx，将游标由ki+1对应的pi+1向下移动一层。
（4）假设只有大于v的ki，那么，无需将i+1，当前的ki和pi就代表了正确的下一层，c = c.pi
以上操作不用递归，直接用while(c不是叶节点)写死即可。
当到达叶节点时，直接顺序遍历，有就是有，没有就是没有。

Range Search

range search有些难。首先先用lb当v遍历树，首先找到目标的leaf node（而不是直接找lb在不在）。
首先找>=lb的最小值Ki
（1）假设Ki可以找到，说明lb并不是大于这个节点。
（2）假设找不到，说明lb大于这个节点。
按照2的情况，通过某些微小的移动将其变为1的情况（将此节点后移，这样ki可能会找到，如果还没有找到，继续后移）
这里不赘述详细的找出lb到ub所有节点的详细步骤，因为本质上是一个单链表的O(m-n)的查找问题，书是用while做的，这个实现因人而异。
B+树的时间复杂度是

N为key的总数目，n为度。详细证明书也没有说，估计是太难了。
其中root基本是在buffer中，因为root是最被频繁hit的节点，所以按照前几章的理论，数据库结构是：磁盘->Buffer Management+LRU（其中磁盘内容以指针混写的方式被存入buffer），显然在这两层之上的一定是一个B+ Tree。因为我们说所谓查找，最后查找的无非是B+树的子节点，那么该节点从何而来呢？也就是该节点的指针到底是指向谁呢？显然一定不会是一个硬盘地址，因为硬盘没有地址，只有内存有地址，声明一个char* p，此p一定是一个内存里的指针，而不是一个硬盘的指针，硬盘没有指针，只有001010010。所以，我们推断B+树一定是指向了Buffer，所有B+树的数据一定是从Buffer中读取的，所有Buffer中的数据一定是从硬盘读取的，不存在跨级的现象。综上所述，为什么访问root基本一定不会在hit磁盘？因为是LRU起的作用。
那么，研究访问root是不是要hit磁盘是否等同于在研究鸡蛋从大头打合适还是小头打合适？非也。
如果我们有1000000个key，度为50，经过计算，B+树节点要被 hit 4次，既然所有B+树节点来自于磁盘，那么等同于磁盘要被hit四次。假设LRU通过优化，将root节点存入buffer，那么磁盘就会被hit三次，性能提高了百分之20。而AVL树要被hit 20次。
对于range search。除了log的复杂度，还需要加上

M为顺序遍历的point数，(n/2)是考虑平均半空的情况。