"organization and maintenance of large ordered indices"这篇论文在1970年由Bayer和McCreight教授提出，可以说是B-tree相关论文的鼻祖，之后b-tree这种数据结构以及各种变体被广泛用于各种存储、数据库系统中。论文详细讲述了b-tree的各种操作、代价、k值的选择以及实验，已经很详细也比较容易理解，本文算不上解析，只作为一个论文笔记，以免日后忘记部分细节可以迅速查看一二。

摘要

适用于动态随机访问文件的索引如何组织和维护？这是这篇论文重点讨论的一个问题。
论文提出一种用于组织页面索引的特殊数据结构，叫作B-tree。对于特定的key，支持数据检索、插入和删除操作，时间复杂度为logk(I)(I为索引的size，k是个可调的自然数)。存储利用率至少为50%，一般情况下会比50%高很多。论文接下来详细分析了这个结构，并对如何选择k值可以获得更佳性能做了分析，文末做了各种场景下的实验。

Introduction

定义一组(x, a) 为索引的单元，key为x，其它相关信息为a。假设索引是很大的，在任一时间段内只有一小部分可以放入内存中，因此bulk操作需要被支持。
实际实验表明在一台IBM 360/44带有2311 disc上，维护一个1.5w大小的索引，平均可达到每秒9次数据索引、插入和删除。通过理论分析，150w大小的索引，在特定参数下每秒至少两个事务是可以达到的。
索引是被组织成定长的page，每个page可以包含2k个keys。page也是主存与磁盘数据传输的单位。每个page是b-tree的一个结点，在这篇论文中树的增长和缩小以split和merge的方式，分裂和连接过程最初发生在叶子结点，可以向上传播直到根结点。如果root分裂了，则产生一个新的root，这也是tree增高的唯一一种方式。树缩小时相反的过程发生。

相比其它的组织方式，b-tree有如下优点：

1. 在任何时刻，存储利用率都至少有50%，由于平均值。
2. 存储的请求和释放只发生在文件增长和缩小时，如果存储容量占比较高时并不会发生阻塞和性能衰退问题。
3. 维护key的顺序，给定一个key可以顺序的查找文件，支持skip，delete和retrive操作
4. bulk操作可以预先对事务排序，提高效率。

b-tree

对于任一一个非空、高度为h的b-tree T都有以下属性：

1. 从root到叶结点的长度都是相同的，为h。
2. 除root和叶结点的其它结点都至少有k+1个孩子。root不为叶结点时至少有2个孩子。
3. 每个结点最多有2k+1个孩子。

b-tree中结点的数目，Nmin为最小数目，Nmax为最大数目，则对于h>=2的b-tree有以下公式，1为root，2对应root最少有两个孩子：

Nmin

相似地：

Nmax

N(T)

数据结构和检索算法

数据结构

数据结构有以下属性：

1. 每个page可以包含k～2k个keys(索引单元)，root可以包含1~2k个keys。
2. 假设e为非叶结点P中key的数目，则P有e+1个sons。

3. P中key都是有有序的，x1 < x2 < x3 ... < xe，另外P中包含e+1个指针，指向P的不同的孩子结点，叶子结点中的指针是未定义的。P的逻辑组织形式如F1中所示。

   
   
   F1

4. 让P(pi)为pi指向的page，让K(pi)为以P(pi)为根结点的最大子树所包含的所有key的集合，对于b-tree来讲，以下条件应该满足：

   
   

F2展示了一个k为2，h为3的满足上述条件的例子。

F2

检索算法

检索逻辑比较简单，如F3所示。在实际编程中，可以使用二分查找定位page中的具体key来提高效率。

F3

检索代价

从检索逻辑中可以看出，最多h个页面需要被扫描，根据上述结点数目的公式可以得出，一个size为I的索引，key的数目：

Ikey

由此可得出h的边界：

h

key的插入

insert逻辑如F4所示流程，先查找到y所对应的结点，如果结点未满(<2k)，直接插入，否则需要split操作。

F4

split

如果P已经有了2k个keys，再插入一个key时会split成两个page，split先将key插入P形成以下序列：
p0, (x1, p1), (x2, p2)...(x2k+1, p2k+1)
将其中的子序列p0, (x1, p1), (x2, p2)...(xk, pk)放入P中，剩余的pk+1, (xk+2, pk+2)...(x2k+1, p2k+1)放入P'中。
Q为P的父亲结点，insert新的entry (xk+1, p')， p'指向P'，P和P'成为兄弟结点。
当然，Q由于新加入了一个key也可能会split，这个过程可能会一直传播到根结点，当根结点split时，产生一个新的page作为新的root结点。

cost

指定fmin(fmax)为page拿取的最小和最大数目
指定Wmin(Wmax)为page written的最小和最大数目

F5

检索代价

fmin = 1; fmax = h
wmin = 0; wmax = 0;

插入代价

fmin = h;
wmin = 1;
如果检索的整个路径包括root结点都需要split时，则整个路径上的page都需要written, 分裂的两个page * h加一个新的root结点。
fmax = h
wmax = 2 * h + 1
虽然最差的情况下，wmax是比较大的，但并不是一个衡量性能的好方式，应该以平均的方式来测量。

如果索引只有查找和插入，没有删除，可以得出平均的work。
首先可以得出在这种情况下构建一个size为I的索引所需要的工作量：每个page split引起一个新的page被创建(root为2个)，因此page分裂的次数最多为n(I) - 1, n(I)为index中page的数目。因为每个page最少含有k个keys，除了root为1，可以得出：n(I) <= (I-1) / k + 1。每次单个page的分裂最多引起两个额外的page被written。因此平均单个key的插入(引起了split)引起的额外page written的边界为：
(n(I) - 1) * 2 / I < 2/k

因此在没有delete的情况下，单次insert所带来的平均page written为：
wa < 1 + 2/k

删除

删除过程

F6中展示了删除一个key并正确维护数据结构的流程。

F6

首先定位到key的位置，为yi，如果在叶子结点直接删除，否则它必须被root为P(pi)子树中的最小key值替代，L为最小值所在的page，最小值x1从L中删除，L可能包含少于k的keys，因此在L和它相邻的兄弟间需要做catenation或者underflow操作。

catenation

如下图所示，P和P'是兄弟结点，有共同的父亲Q，如果P和P'中的key的数目加起来不超过2k，P和P'可以连接成一个page。将(yj,p')从Q中删除，同样的问题在Q中也可能发生，可以一直传播到根结点。

catenation

underflow

如果两个page中的key数目超出了2k，将两个page中的key等同划分，首先将P与P'连接起来形成大P，这时P在内存中，然后将P从中间分裂(如上述split中描述)。
注意underflow不会传播，Q会被修改，但是Q中key的数量没有变化。

删除的代价

y在叶子结点中：
fmin = h; wmin = 1;
y在非叶结点，y所在的page和子树中最小key所在的page：
f = h; w =2
如果除了开始的两个page发生了连接，检索路径上root的其它孩子结点都发生了underflow操作(最多一次)，root被修改了：
fmax = 2*h -1; wmax = h + 1

如insert一样，wmax对于衡量一次delete操作带来的工作量意义不大。更有用的方式应该是计算平均代价。
考虑没有insert只有delete的场景，如果没有连接和underflow，f1=h，w1=2是最差的情况。
每次delete最多引起最多一次underflow，一次underflow会带来一次拿取f2=1和两次写入w2=2。
最多带来n(I) - 1次连接，也就是(I-1) / k，每次连接带来1次额外的拿取和2次写入，所以可以得出平均值：

del

page overflow和存储利用率

当每个page包含k个keys时，存储利用率低至50%。利用率可以通过避免split来提升。

overflow

P和P'是相邻的兄弟结点，假设key需要insert到P中，并且P已经满了而P‘并没有满，则key可以insert到P中，再如上文所述underflow的操作，与P'中的key一起划分。这种方式避免了split，因此只有page和相邻的兄弟结点都满了才会做split操作。
在没有delete的场景下，overflow将会提升最差利用率到66%。如果insert和delete都存在，利用率还是会退化到50%。
代价：
fmin = h; wmin = 1;
fmax = 3 * h - 2; wmax = 2 * h + 1; (??)

average:
fa < h + 2 + 2/k
wa < 3 + 2/k

带有插入和删除的索引维护代价

这一节列举了几种场景下的例子和相应的代价。通过分析可以得出scheme的性能取决于实际insert和delete操作的序列。相比单独的insert或者delete操作，交互的insert和delete操作会降低性能，不过最差也只会降低三倍。
在论文的实验中，带有overflow的测试性能要好于禁止overflow的性能。

F7

k值的选择

这个方案的性能取决于k值。
为了获得一个对性能粗略的估计，有如下假设：

1. 每个page written和fetched的时间花费以如下形式表示：

   
   
   
   

   a: 每个page花费的固定时间，例如平均磁盘访问时间加上CPU的固定overhead等。
   B: 每个page中的entry的传输时间。
   r： 时间对数部分的常数，例如二分查找。
   v：平均页面占用率系数

假设修改一个页面不要求移动page中的keys，但在主存中连接几个信息片段写入page中的子命令是不可少的。这是假设fetch和write一个page所花费相同时间的原因。

1. 在retievals、insertion和deletion的混合场景下，每个事务拿取和写入page的数目大约为h，每个事务的总时间花费大约为：

   
   
   
   

   对于size为I的索引，树的高度h大约为：

   
   
   
   可以得到：
   
   
   

   当k值选定时，可以获得Ta的最小值：

   
   

假设a=50ms，B=90us，根据F8中数值，可接受的选择 64<k<128，为了编程遍历，选择k=60，一个page 120个entries。

F8

选择k=60，对于确定的高度，index的size如F9所示：

F9

实验结果

本节略