B树的C++实现

简介

https://en.wikipedia.org/wiki/B-tree

B树也属于平衡树，空间复杂度O(n)，查询/插入/删除的时间复杂度都是O(log(n))。
适用于大块数据的存储操作，相比其他树型结构可以降低很多磁盘io，广泛用于数据库和文件系统。是一些更高级算法的基础。

knuth的定义(The art of computer programming)

一棵m阶B树(a btreee of order m)
1. 每个节点最多有m个子节点。
2. 除了根和叶子，每个节点至少有m/2个子节点。
3. 根最少有2个子节点，除非它也是叶子。
4. 所有叶子都在同一层上，且不包含具体数据。
5. 每个有k个子节点的非叶子节点，都包含k-1个key。

其他性质或情景

• 目的是存大量的key。可以快速增删查某个key。
• 规定不存在重复的key
• 实际应用中一个节点可能包含上千个key。key对应的数据也存在同个节点，这里我们忽略数据，只看key。
• 如果树的节点总数为n，那么树的高度为O(log(n))这个级别，就是说高度和节点总数为对数关系，所以高度相对会很低。
  做成图像的话，与其他树型结构相比，是一棵矮胖的树。

  

• 先简单观察一个例子，这棵B树存了一系列数字。
  根存2个key 50，100，有3个子节点。
  key其实充当分隔的角色，n个key可以把数据范围分隔成n+1段，对应n+1个子节点。
  搜索时就按这个分隔来。比如搜索27。50和100把数分割成三段，27落在第一段，那么对应[20，46]这个子节点。又落在中间一段，那么走到[27, 30]。(要判断一下作为分割者的key，比如搜20的话，走到[20, 46]时直接就找到了)
  这样已经走到叶子[27, 30]，找到27。
  如果叶子里找不到，就是不存在。

为什么B树可以降低磁盘io

• 一般把系统存储实体分为主副两块(primary/secondary)，简单对应就是内存和硬盘。

• 读写硬盘比读写内存慢了多个数量级，因为硬盘读写包含了机械操作，类似唱片机。
  读一个地址需要转动，定位，一套操作下来，相同的时间内可能可以读写内存上万次。
  读磁盘数据时按页来的，典型是2k到16k字节。

• 按上述情况，从磁盘读一块数据比用cpu处理这块数据慢得多。
  那么可考察两个值：

  1. 磁盘io次数
  2. cpu计算时长
• 磁盘io次数可看成一次磁盘读或写数据的总页数。
  这里不是绝对精确，因为每次磁盘读写耗时不一定是一样的，机械臂移动的距离不一样。
  但总体对比仍是准确的。

• 一个典型的B树应用中，数据量是非常大的，不是所有数据都能装到内存里。
  B树算法只会按需把数据页放到内存，在内存中保留固定页数的数据。这样B树不会受一台计算机的内存大小限制。

• 可以这样对数据操作来建模，x表示一个逻辑物体，磁盘读(x)表示从磁盘读这个物体的数据，磁盘写(x)表示往磁盘写入这个物体的数据。
  那么典型的对x的一次读写操作可以表示成

  1. 准备读x
  2. 磁盘读(x)
  3. cpu处理x在内存中的数据
  4. 磁盘写(x)
  5. 其他内存操作
• 因为磁盘读(x)和磁盘写(x)占了耗时的大部分，且不可避免，所以得让一次磁盘操作尽量多处理数据。
  那么在实际算法中得体现就是，一个节点中key的数量很大，实用中通常取值50到2000。
  因为是树型指数级的关系，节点分叉数的微小增长就能快速减小整个树的高度，也就是减小了搜索次数，也就是减小了读磁盘的次数。
  例如每个节点存1000个key，只需3层就能存1002001000(10亿)个key。

<<算法导论>>的定义

1. 每个节点x的属性

   • 节点存有x.n个key
   • key以非降序排列。即x.key1 <= x.key2 …. <= x.key(x.n)
   • x.leaf标识是否为叶子，非叶子节点又称为内部节点(internal node)
2. 每个内部节点x存有x.n+1个类指针数据c(x.c1,x.c2 … x.c(x.n+1))，每个指向对应的下一层节点。
   叶子没有下一层，不存指针。

3. 节点里的key把key空间分割成k.n+1份。c其实就对应被key分割出来的n+1个范围。

4. 所有叶子的高度相同，即树的高度。

5. 节点有key的高低数量限制。定义一个大于等于2的值t，为B树的最小度(minimum degree)。其实就是knuth定义里的阶除以2。这里用minimum degree，不用除法，感觉舒服一些。

   • 除了根，所有节点至少含有t-1个key，即至少有t个子节点。
     如果树不是空的，根至少得有1个key。
   • 每个节点最多有2t-1个key。因此最多只能有2t个子节点。
     如果节点有2t-1个key，就说它是满的(full)。

这个最小度(minimum degree)是实用时我们可调的参数。它限定了每个节点里的key数范围。

B树的操作

两个约定

1. B树的根节点总是已经在内存中，不需要磁盘读()操作。当根节点改变时，磁盘写()还是需要的。
2. 所有函数的节点参数都必须已经进行过磁盘读()操作。

我按算法导论的流程来实现插入等操作，按wikipedia的流程实现删除操作。

搜索

从节点x开始搜索k

btree_search(x, k):
    if x.leaf:
        return None

    i = 1
    while i <= x.n and k > x.key[i]:
        i += 1
    if i <= x.n and k == x.key:
        return x, i
    else:
        磁盘读(x.c[i]
        btree_search(x.c[i]], k)

• 和二分差不多
• 如果是叶子，说明没找到，返回None。
• 遍历当前节点的key，如果碰到相等的，说明找到了，直接返回节点和位置(x, i)。
  如果碰到一个大于k的，k一定是落在这个key之前的分割范围内，对应c[i]]。
  那么得先从磁盘读x.c[i]的数据，再往子节点搜索。
  这里遍历可以改成二分查找。

• 设总结点数为N，那么搜索层数方面的复杂度是O(Log(t, N))。每层遍历的复杂度是O(t)。
  整体CPU的耗时是O(tLog(t, N))。

初始化

btree_create():
    x = 分配新节点()
    x.leaf = True
    x.n = 0
    磁盘写(x)
    return x

• 初始化一个空的B树。O(1)磁盘操作和O(1)CPU时间。

插入key

• B树的插入比一般二叉树复杂，二叉树是直接添加一个叶子，B树是往节点添加一个key。
  但B树的节点有容量限制。如果要往节点y插入key，但发现y满了(有2t-1个key)，得找到中间的y.key[t]，把它拿出来挪到y的父节点里，剩下的两边分成两个包含t-1个key的节点。
• y挪到上层后把原来y对应的范围分割成两个范围，原来y节点分裂出来的两个新节点正好对应两个新范围。
  这个操作叫分裂(split)。即一个满的2t-1个key的节点拿出一个key放到父节点，再变成两个t-1的节点。

把分裂操作写成一个函数，对节点x的第i-1和第i个key之间对应的子节点进行分裂。

btree_split_child(x, i):
    y = x.c[i] // 原来的子节点写为y
    z = 分配新节点()
    把y的后t-1个key复制到z
    把y的第t个key插到x的i之前
    z.n = t-1
    y.n = t-1
    x.n += 1
    更新x的子节点的对应
    磁盘写(y)
    磁盘写(z)
    磁盘写(x)

图中对[120, 128, 200]这个节点进行分裂。

• 问题来了，父节点会不会也是满的？不会。
  插入操作是从顶层的根节点往下走，会不断检查子节点是不是满的，如果满了会先把它分裂。从而保证key数量不会超2t-1。
  先不考虑根节点，做一个通用的插入函数。规定当前节点必须不是满的。

btree_insert_nonfull(x, k):
    if x.leaf:
        找到k的位置(第一个大于它的key之前，或末尾)插入
        x.n += 1
        磁盘写(x)
    else:
        同样找出插入位置i
        磁盘读(x.c[i]) # 读出子节点数据
        if x.c[i].n == 2t-1: # 如果已满，做分裂。
            btree_split_child(x, i)
            判断提上来的key，决定接下来往左还是往右走。
        btree_insert_nonfull(x.c[i], k) # 往下走

• 如果是叶子，插入。
  否则找到key所在的范围对应的子节点。
  如果该子节点已满，先做分裂，再往左边的新子节点递归插入key。
  如果没满，直接往子节点递归插入key。

完整的插入函数从根节点T开始。

btree_insert(T, k):
    if T.n == 2t-1: # 根满了
        s = 分配新节点()
        T变为s的子节点
        s变为根节点
        btree_split_child(s, 1) # 原来的根节点作为子节点进行分裂

    btree_insert_nonfull(新根节点, k)

• 可发现B树的高度只在根节点分裂时才+1。原来的根分裂成两个节点，中间的key提上去变成新的根。
• key最终都是插入到叶子节点。
• 操作过程始终要保证节点key数在t-1到2t-1之间的性质。
• 插入后key满是合法的，不用管。等下次插入时会进行split。
• 上述操作是one pass，即从上到下一遍完成。也可以先插入，再从下往上按需进行分裂，可能更容易理解，但效率稍低。

删除一个key

• 先找到key。如果存在的话，删除key，并保证树仍然满足B树的key数限制。
• 有两种策略，与插入类似。一是从根开始一遍完成，二是先找到要删除的key，再按情况重构(rebalance)使它维持平衡。这里用第二种，较直观。

先找到key所在节点

如果是叶子节点
    从节点删除key
    如果剩余key数大于等于t-1，返回成功。
    否则进行rebalance

如果是内部节点
    找到key左边子节点开始的子树里的最大key a，也就是子树右下角的key(必然是在最底层的叶子节点)。
    如果key所在节点的key数大于t-1，可直接用a替代key即可。不用做其他操作。
    否则可同样尝试右边子树，找右边子树的最小key。
    如果都无法直接替换，就强行用左边的a来替换key，再从a原来的节点开始做rebalance。

• rebalance一定是从叶子节点开始。通常是从同一层的兄弟节点取一个key。如果兄弟节点的key不够，需要做merge操作。
  merge操作从父节点拉一个key下来，放在中间，和左右子节点的key合并。
  会导致父节点减少一个key，这时如果父节点的key小于t-1，就得对父节点再做rebalance，这样形成一个递归的模式。有可能一直往上返到根节点才结束。

rebalance(节点n)
    如果左边兄弟节点key数大于等于t-1。做一个顺时针旋转，把左边兄弟节点最大的key替换父节点的key，父节点原来的key挪到n的key打头位置。
    如果左边不行，尝试右边的对称操作。
    如果都不行，做merge。
    把父节点的key接到左兄弟最右边，把n的所有key再接到最右边。
    这时父节点就减少了一个key。如果key不够，rebalance(父节点)。

删除key图示

重申一些性质：
* 稳定状态下(非操作中)，一个节点可能是满的。
* 如果非叶子节点有n个key，那么一定有n+1个子节点。
* 叶子都在同一层。
* 根最少可以只有1个key

这个树minimum degree为3。那么非根节点的key数必须为2到5。

先搜索key

1. 如果key在叶子
   • 如果叶子key数大于t-1。例如图中的36、38、39、61、62、63、66，直接删除即可。
   • 否则删除后走rebalance。
2. key在内部节点
   • 比如删除40。左子树最大key为39，39所在节点key数大于t-1，可以直接把39挪到40的位置即可。
   • 同样可以找右子树，比如删除35，用36替换即可。
   • 又例如删除60，找右子树里的61替换即可。
   • 如果左右的替换都会造成子节点key数不够，只能先强行替换，再走rebalance。
     比如删除30，取29或32都会造成节点key数不够。那么选29替换，再对[28]这个节点做rebalance。
3. rebalance(节点n)
   • 看左边兄弟节点，如果key数大于t-1，做顺时针旋转即可。
   • 比如删除50后，46代替50，对剩下的42作rebalance，左边key有多余，拿出最末的39代替40，40转下来放到节点n的头部。
   • 如果左边不行尝试右边。

   • 如果都不行，做merge。

     • 比如删除30，造成29替换30，剩下28，28左边兄弟key数不够，右边又没有兄弟。要对28这个节点做merge。
       

       

     • merge分不分左右？写代码时会发现可以处理一下，只写一个方向的就行。

     • 把25拉下来接到左边兄弟最后，把节点n所有节点再接到它最后，变成[16,17,25,28]，父节点变成[15]。
     • 这时父节点的这个key没了，节点n也空了。可把n删除。
     • merge后的节点key数一定不会超标。
       因为左边兄弟最多t-1，否则直接拿过来就行。本身必然是t-2，否则不用走rebalance。再加上拉下来的1，结果是t-1+t-2+1=2t-2。
     • 这时要检查父节点key数，因为被拉下去一个key。
     • 如果父节点不是根
       • 如果剩余key数大于等于t-1。成功返回。
       • 否则走rebalance(父节点)。

     • 如果父节点是根

       • 如果剩余key数大于0。成功返回。
       • 否则父节点唯一的key被拉下来merge到了新节点。把这个新节点作为新的根即可。

         

         如图，如果红色节点存在，merge即可，根还有一个key60。
         如果红色节点不存在，merge时把29拉下来造成根节点为空。那么直接让merge出来的节点成为根即可。

4. 子树问题

   • rebalance走到内部节点时要考虑子树问题。这个很多资料没有说明。
     比如现在父节点只有一个15了。rebalance发现右边兄弟有3个key，按说是逆时针旋转29和35，但是35的左子树怎么办？
     看下35的子树区间，强行替换后35的左子树区间为[29, 35]，发现如果旋转后把35的左子树变成29的右子树刚好能解决问题。

     

     如图。29转下来，35转上去，35的左子树变成29的右子树。

• 内部节点merge不需要处理子树，merge完判断一下是否要rebalance父节点即可。

  

  如图，如果红色节点不存在，进行merge，不需要处理子树。

测试

测试其实很有讲究。这里没能力去总结。只做简单测试，尽量保证逻辑正确。并记录一下平均操作耗时。

1. 确定数据量比如100000个随机数。依次插入。
2. 随机搜索插入过的、未插入过的数，看是否找的到。
3. 随机删除插入过的、未插入过的数。再搜索。
4. 检测数据总量是否正确。可做一一对比。
5. 删除所有数据并检查。
6. 发挥想象

记录所有操作的耗时。观察内存占用。
这里简单测试，不再做图。
插入的总key数100万。
md递增，从2到1000。

CPU是intel i5 6600k 3.5GHz

Btree PrintInfo:
md = 2
total_nodes = 1000000
height = 16
test_0_result avg time 10131 nanoseconds 插入所有
test_1_result avg time 6340 nanoseconds 查询所有
test_2_result avg time 6668 nanoseconds 查询不存在的
test_3_result avg time 8100 nanoseconds 插入已存在的
test_4_result avg time 11432 nanoseconds 删除存在的
test_5_result avg time 7524 nanoseconds 查询被删除的
test_6_result avg time 7073 nanoseconds 查询没被删除的
test_7_result avg time 4175 nanoseconds 删除不存在的
test_8_result avg time 200 nanoseconds 查询节点数
test_9_result avg time 11172 nanoseconds 删除所有
test_10_result avg time 200 nanoseconds 查询节点数
test_11_result avg time 10539 nanoseconds 插入所有
test_12_result avg time 300 nanoseconds 查询节点数

Btree PrintInfo:
md = 5
total_nodes = 1000000
height = 8
test_0_result avg time 4792 nanoseconds 插入所有
test_1_result avg time 3475 nanoseconds 查询所有
test_2_result avg time 3617 nanoseconds 查询不存在的
test_3_result avg time 3607 nanoseconds 插入已存在的
test_4_result avg time 4780 nanoseconds 删除存在的
test_5_result avg time 3653 nanoseconds 查询被删除的
test_6_result avg time 3494 nanoseconds 查询没被删除的
test_7_result avg time 2734 nanoseconds 删除不存在的
test_8_result avg time 200 nanoseconds 查询节点数
test_9_result avg time 5182 nanoseconds 删除所有
test_10_result avg time 200 nanoseconds 查询节点数
test_11_result avg time 4876 nanoseconds 插入所有
test_12_result avg time 200 nanoseconds 查询节点数

Btree PrintInfo:
md = 10
total_nodes = 1000000
height = 6
test_0_result avg time 3707 nanoseconds 插入所有
test_1_result avg time 2853 nanoseconds 查询所有
test_2_result avg time 3019 nanoseconds 查询不存在的
test_3_result avg time 2710 nanoseconds 插入已存在的
test_4_result avg time 3773 nanoseconds 删除存在的
test_5_result avg time 2897 nanoseconds 查询被删除的
test_6_result avg time 2778 nanoseconds 查询没被删除的
test_7_result avg time 2296 nanoseconds 删除不存在的
test_8_result avg time 200 nanoseconds 查询节点数
test_9_result avg time 4069 nanoseconds 删除所有
test_10_result avg time 200 nanoseconds 查询节点数
test_11_result avg time 3614 nanoseconds 插入所有
test_12_result avg time 200 nanoseconds 查询节点数

Btree PrintInfo:
md = 20
total_nodes = 1000000
height = 5
test_0_result avg time 3267 nanoseconds 插入所有
test_1_result avg time 2399 nanoseconds 查询所有
test_2_result avg time 2471 nanoseconds 查询不存在的
test_3_result avg time 2241 nanoseconds 插入已存在的
test_4_result avg time 3648 nanoseconds 删除存在的
test_5_result avg time 2481 nanoseconds 查询被删除的
test_6_result avg time 2385 nanoseconds 查询没被删除的
test_7_result avg time 2016 nanoseconds 删除不存在的
test_8_result avg time 500 nanoseconds 查询节点数
test_9_result avg time 3906 nanoseconds 删除所有
test_10_result avg time 200 nanoseconds 查询节点数
test_11_result avg time 3344 nanoseconds 插入所有
test_12_result avg time 200 nanoseconds 查询节点数

Btree PrintInfo:
md = 50
total_nodes = 1000000
height = 4
test_0_result avg time 3731 nanoseconds 插入所有
test_1_result avg time 2115 nanoseconds 查询所有
test_2_result avg time 2207 nanoseconds 查询不存在的
test_3_result avg time 1888 nanoseconds 插入已存在的
test_4_result avg time 4377 nanoseconds 删除存在的
test_5_result avg time 2180 nanoseconds 查询被删除的
test_6_result avg time 2102 nanoseconds 查询没被删除的
test_7_result avg time 1828 nanoseconds 删除不存在的
test_8_result avg time 200 nanoseconds 查询节点数
test_9_result avg time 4679 nanoseconds 删除所有
test_10_result avg time 200 nanoseconds 查询节点数
test_11_result avg time 3700 nanoseconds 插入所有
test_12_result avg time 300 nanoseconds 查询节点数

Btree PrintInfo:
md = 100
total_nodes = 1000000
height = 3
test_0_result avg time 4970 nanoseconds 插入所有
test_1_result avg time 1866 nanoseconds 查询所有
test_2_result avg time 1961 nanoseconds 查询不存在的
test_3_result avg time 1561 nanoseconds 插入已存在的
test_4_result avg time 5915 nanoseconds 删除存在的
test_5_result avg time 1989 nanoseconds 查询被删除的
test_6_result avg time 1849 nanoseconds 查询没被删除的
test_7_result avg time 1646 nanoseconds 删除不存在的
test_8_result avg time 300 nanoseconds 查询节点数
test_9_result avg time 6458 nanoseconds 删除所有
test_10_result avg time 200 nanoseconds 查询节点数
test_11_result avg time 4891 nanoseconds 插入所有
test_12_result avg time 300 nanoseconds 查询节点数

Btree PrintInfo:
md = 200
total_nodes = 1000000
height = 3
test_0_result avg time 7941 nanoseconds 插入所有
test_1_result avg time 1867 nanoseconds 查询所有
test_2_result avg time 1986 nanoseconds 查询不存在的
test_3_result avg time 1577 nanoseconds 插入已存在的
test_4_result avg time 9201 nanoseconds 删除存在的
test_5_result avg time 1956 nanoseconds 查询被删除的
test_6_result avg time 1855 nanoseconds 查询没被删除的
test_7_result avg time 1630 nanoseconds 删除不存在的
test_8_result avg time 200 nanoseconds 查询节点数
test_9_result avg time 10544 nanoseconds 删除所有
test_10_result avg time 200 nanoseconds 查询节点数
test_11_result avg time 7712 nanoseconds 插入所有
test_12_result avg time 300 nanoseconds 查询节点数

Btree PrintInfo:
md = 500
total_nodes = 1000000
height = 3
test_0_result avg time 16252 nanoseconds 插入所有
test_1_result avg time 1795 nanoseconds 查询所有
test_2_result avg time 1895 nanoseconds 查询不存在的
test_3_result avg time 1531 nanoseconds 插入已存在的
test_4_result avg time 24504 nanoseconds 删除存在的
test_5_result avg time 1879 nanoseconds 查询被删除的
test_6_result avg time 1789 nanoseconds 查询没被删除的
test_7_result avg time 1572 nanoseconds 删除不存在的
test_8_result avg time 200 nanoseconds 查询节点数
test_9_result avg time 22461 nanoseconds 删除所有
test_10_result avg time 200 nanoseconds 查询节点数
test_11_result avg time 16335 nanoseconds 插入所有
test_12_result avg time 300 nanoseconds 查询节点数

Btree PrintInfo:
md = 1000
total_nodes = 1000000
height = 2
test_0_result avg time 30469 nanoseconds 插入所有
test_1_result avg time 1645 nanoseconds 查询所有
test_2_result avg time 1748 nanoseconds 查询不存在的
test_3_result avg time 1286 nanoseconds 插入已存在的
test_4_result avg time 49086 nanoseconds 删除存在的
test_5_result avg time 1744 nanoseconds 查询被删除的
test_6_result avg time 1637 nanoseconds 查询没被删除的
test_7_result avg time 1444 nanoseconds 删除不存在的
test_8_result avg time 200 nanoseconds 查询节点数
test_9_result avg time 42441 nanoseconds 删除所有
test_10_result avg time 300 nanoseconds 查询节点数
test_11_result avg time 30501 nanoseconds 插入所有
test_12_result avg time 200 nanoseconds 查询节点数

• 可以看到随md增大，插入时间从大变小再变大。
  • 变小是因为md越大，树高度越小。是在较大空间内进行少数几次二分查找，而不在较小的空间内进行多次二分查找。每次深入子节点都是换空间，读的实际内存和磁盘可能根之前空间有距离。我们目前的数据应该用不到磁盘，但是原理是一样的，实用时进入子树可能会读一大块磁盘数据。
  • 后来又变慢，是因为节点存key用的vector数组，插入后需要把插入点之后的所有数据更新一遍，量大时效率很低。
• 随md增大，查询是越来越快。因为空间转换次数变少，且在数组的连续空间里，key在1000这个级别，二分查找很快。

• 随md增大，插入已存在的也是越来越快，因为已存在，不用插入，相当于查找。

• 随md增大，删除是先变快再变慢。原因和插入类似。

总结

• wikipedia的删除操作讲的比较清晰
• 优化问题
  有的操作可以省略，比如删除再rebalance。删除时会移动大批数据，rebalance时又可能会填进去，造成重复劳动。
  vector问题。插入头部效率低，需要移动所有数据。
  我的代码是很朴素的实现，没有处理这些问题。
• 整个算法还是相对容易。对着流程和图示调试就行。需要注意各种边界，注意数据改变时的更新，很容易漏更新。
• 做一个打印整棵树的函数。非常香。
• 调试数据做100个key多试几次，基本可以覆盖所有错误情况。
• 如果树很大，调试也不用看全部的节点，只需看小范围节点，基本跟踪个一两层就能发现问题。

参考

https://en.wikipedia.org/wiki/B-tree
<<算法导论>>
https://cstack.github.io/db_tutorial/
https://www.programiz.com/dsa/b-tree
https://dzone.com/articles/database-btree-indexing-in-sqlite
https://scanftree.com/Data_Structure/deletion-in-b-tree
https://www.cs.yale.edu/homes/aspnes/pinewiki/BTrees.html
https://www.geeksforgeeks.org/introduction-of-b-tree-2/
https://www.codercto.com/a/83791.html
https://www.cs.cornell.edu/courses/cs3110/2012sp/recitations/rec25-B-trees/rec25.html
https://github.com/google/btree

代码

BTree.h

// btree
// 20210216 xc 

#pragma once

#include <iostream>
#include <memory>
#include <vector>
#include <deque>
#include <tuple>
#include <cassert>

class BTreeNode
{
    friend class BTree;

    std::vector<int> keys;
    std::vector<std::shared_ptr<BTreeNode>> children;
    //std::deque<int> keys;
    //std::deque<std::shared_ptr<BTreeNode>> children;
    std::shared_ptr<BTreeNode> pnt;

    bool is_leaf;
    int key_count; // key_count == keys.size()
    int pnt_pos; // parent's children index. pnt->children[pnt_pos] == me

public:
    BTreeNode();
    BTreeNode(std::shared_ptr<BTreeNode> n, int i);
};

BTreeNode::BTreeNode():keys(0), children(0)
{
    this->key_count = 0;
    this->is_leaf = true;
    this->pnt = nullptr;
    this->pnt_pos = 0;
}

BTreeNode::BTreeNode(std::shared_ptr<BTreeNode> n, int pos)
{
    // copy data from pos to new node

    this->key_count = n->key_count / 2;
    this->is_leaf = n->is_leaf;
    this->pnt_pos = n->pnt_pos;

    this->keys = std::vector<int>(this->key_count);
    //this->keys = std::deque<int>(this->key_count);

    for (int i = 0, j = n->key_count / 2 + 1; i < this->key_count; ++i, ++j)
        this->keys[i] = n->keys[j];

    if (!n->is_leaf)
    {
        this->children = std::vector<std::shared_ptr<BTreeNode>>(this->key_count + 1, nullptr);
        //this->children = std::deque<std::shared_ptr<BTreeNode>>(this->key_count + 1, nullptr);

        for (int i = 0, j = n->key_count / 2 + 1; i <= this->key_count; ++i, ++j)
        {
            this->children[i] = n->children[j];
            this->children[i]->pnt_pos = i;
        }
    }
}

class BTree
{
private:
    std::shared_ptr<BTreeNode> root;
    int md; // minimum degree
    int height;
    int total_keys;
    int total_nodes;

    int SplitChild(std::shared_ptr<BTreeNode> n, int i);
    int InsertNonFull(std::shared_ptr<BTreeNode> n, int key);
    std::tuple<int, std::shared_ptr<BTreeNode>, int> SearchKey(std::shared_ptr<BTreeNode> n, int key);
    int Rebalance(std::shared_ptr<BTreeNode> n);
    int Destroy(std::shared_ptr<BTreeNode> n);
    void PrintNode(std::shared_ptr<BTreeNode> n, int level);


public:
    int PrintInfo();
    int Insert(int key);
    int Find(int key);
    int Delete(int key);
    int TotalNodes();
    int TotalKeys();
    void PrintTree();
    BTree();
    BTree(int md);
    ~BTree();
};

BTree::BTree()
{
    std::cout << "Btree born" << std::endl;

}

BTree::~BTree()
{
    std::cout << "Btree die" << std::endl;

    this->Destroy(this->root);
}

BTree::BTree(int md)
{
    std::cout << "Btree born" << std::endl;
    this->md = md;
    this->height = 1;
    this->total_keys = 0;
    this->total_nodes = 1;

    root = std::make_shared<BTreeNode>();


}

void BTree::PrintNode(std::shared_ptr<BTreeNode> n, int level)
{
    if(n->is_leaf)
        std::cout << "leaf-";
    std::cout << "[count "<<n->key_count<<"][pnt_pos "<<n->pnt_pos <<"]node=";
    for (int i = 0; i < n->keys.size(); ++i)
    {
        std::cout << n->keys[i] << "-";
    }
    std::cout << std::endl;

    if (n->is_leaf)
        return;


    for (int i = 0; i < n->children.size(); ++i)
    {
        for (int i = 0; i < level * 8; ++i)
            std::cout << " ";
        std::cout << "child-" << i <<"-";

        assert(n->children[i]->pnt == n);


        PrintNode(n->children[i], level + 1);
    }
}

void BTree::PrintTree()
{
    PrintInfo();
    PrintNode(this->root, 1);
}

int BTree::SplitChild(std::shared_ptr<BTreeNode> n, int pos) // 分裂index为i-1和i之间的子节点。子节点一定是满的才分裂。
{
    //std::cout << "SplitChild" << std::endl;
    auto cn = n->children[pos];

    auto new_right = std::make_shared<BTreeNode>(cn, cn->key_count / 2 + 1);

    new_right->pnt = n;
    new_right->pnt_pos ++;

    // insert into n
    n->keys.resize(n->keys.size() + 1);
    n->children.resize(n->children.size() + 1);
    for (int j = n->key_count; j > pos; --j) // 效率低
    {
        n->keys[j] = n->keys[j - 1]; // move forward
        n->children[j + 1] = n->children[j]; // move forward
    }

    n->keys[pos] = cn->keys[cn->key_count / 2];
    n->children[pos + 1] = new_right;

    cn->keys.resize(cn->key_count / 2);
    cn->children.resize(cn->key_count / 2 + 1);
    cn->key_count /= 2;

    n->key_count++;

    // update pnt
    if(!new_right->is_leaf)
        for (int i = 0; i <= new_right->key_count; ++i)
            new_right->children[i]->pnt = new_right;

    this->total_nodes++;
    return 0;
}

int BTree::InsertNonFull(std::shared_ptr<BTreeNode> n, int key)
{
    if (n->key_count == 0 && n->is_leaf)
    {
        n->keys.push_back(key);
        n->key_count++;

        return 0;
    }

    // binary search
    int i = 0, j = n->key_count - 1, pos = 0, temp_key = 0;
    for (;;)
    {
        if (i == j) // 2 slots
        {
            if (n->keys[i] == key)
                return 1;

            if (n->keys[i] > key)
                pos = i;
            else
                pos = i + 1;

            break;
        }
        if (i + 1 == j) // 3 slots
        {
            if (n->keys[i] == key || n->keys[j] == key)
                return 1; // exists

            if (n->keys[i] > key)
                pos = i;
            else if (n->keys[j] < key)
                pos = j + 1;
            else
                pos = j;

            break;
        }

        pos = (i + j) / 2;
        temp_key = n->keys[pos];
        if (temp_key == key)
            return 1; // exists

        if (temp_key > key)
            j = pos;
        else
            i = pos;
    }

    if (n->is_leaf)
    {
        n->keys.resize(n->key_count + 1);
        for (int i = n->key_count; i > pos; --i) // 效率低
            n->keys[i] = n->keys[i - 1]; // move forward
        n->key_count++;

        n->keys[pos] = key;
        return 0;
    }
    else
    {
        auto cn = n->children[pos];

        if (cn->key_count >= this->md * 2 - 1)
        {
            auto result = SplitChild(n, pos);

            // update pnt_pos
            for (int i = pos + 2; i <= n->key_count; ++i)
                n->children[i]->pnt_pos = i;

            // check the center key
            if (n->keys[pos] == key)
                return 1;

            if (n->keys[pos] < key)
                ++pos;
        }

        return InsertNonFull(n->children[pos], key);

    }
}

int BTree::Insert(int key)
{
    //std::cout << "Insert "<< key << std::endl;
    if (this->root->key_count >= this->md * 2 - 1) // root is full
    {
        //std::cout << "Insert new_root" << std::endl;
        auto new_root = std::make_shared<BTreeNode>();

        new_root->is_leaf = false;
        new_root->children.push_back(this->root);

        this->root->pnt = new_root;
        this->root->pnt_pos = 0;

        this->root = new_root;
        this->total_nodes++;

        SplitChild(this->root, 0);
        this->height++;

        //PrintTree();
    }

    auto result = InsertNonFull(this->root, key);
    if (result == 0)
    {
        this->total_keys++;
    }

    //PrintTree();
    return result;
}

int BTree::Find(int key)
{
    //PrintTree();

    int result, pos;
    std::shared_ptr<BTreeNode> node;

    std::tie(result, node, pos) = SearchKey(this->root, key);

    return result;
}

int BTree::TotalKeys()
{
    return this->total_keys;
}

int BTree::TotalNodes()
{
    return this->total_nodes;
}

std::tuple<int, std::shared_ptr<BTreeNode>, int> BTree::SearchKey(std::shared_ptr<BTreeNode> n, int key)
{
    //std::cout << "Search "<<key << std::endl;

    if (n->key_count == 0) // fail
        return std::tuple<int, std::shared_ptr<BTreeNode>, int>(0, nullptr, 0);

    // binary seatch
    int i = 0, j = n->key_count - 1, pos = 0, temp_key = 0;
    for (;;)
    {
        if (i == j)
        {
            if (n->keys[i] == key)
                return std::tuple<int, std::shared_ptr<BTreeNode>, int>(1, n, i);

            if (n->keys[i] > key)
                pos = i;
            else
                pos = i + 1;

            break;
        }
        if (i + 1 == j)
        {
            if (n->keys[i] == key)
                return std::tuple<int, std::shared_ptr<BTreeNode>, int>(1, n, i);

            if (n->keys[j] == key)
                return std::tuple<int, std::shared_ptr<BTreeNode>, int>(1, n, j);

            if (n->keys[i] > key)
                pos = i;
            else if (n->keys[j] < key)
                pos = j + 1;
            else
                pos = j;

            break;
        }

        pos = (i + j) / 2;
        temp_key = n->keys[pos];
        if (temp_key == key)
            return std::tuple<int, std::shared_ptr<BTreeNode>, int>(1, n, pos);

        if (temp_key > key)
            j = pos;
        else
            i = pos;
    }

    if (n->is_leaf) // fail
        return std::tuple<int, std::shared_ptr<BTreeNode>, int>(0, nullptr, 0);
    else
        return SearchKey(n->children[pos], key);
}

int BTree::Delete(int key)
{
    //std::cout << "!!!!!!!!!!!!!!!!!Delete "<< key << std::endl;
    //PrintTree();

    int result, pos;
    std::shared_ptr<BTreeNode> n;

    std::tie(result, n, pos) = SearchKey(this->root, key);

    if (result == 0) // not found
        return 1;

    if (n->is_leaf)
    {
        for (int i = pos; i < n->key_count - 1; ++i)
        {
            n->keys[i] = n->keys[i + 1];
        }
        n->keys.pop_back();
        n->key_count--;

        if (n->key_count >= (this->md - 1) || this->root == n)
        {
            this->total_keys--;
            return 0;
        }

        auto result = Rebalance(n);
        if (result == 0) // ok
        {
            this->total_keys--;
            return 0;
        }
        else
        {
            return result;
        }
    }
    else
    {
        // search left subtree
        auto left_node = n->children[pos];

        for (;;)
        {
            if (left_node->is_leaf)
                break;

            left_node = left_node->children.back();
        }

        if (left_node->key_count >= this->md) // can grab
        {
            n->keys[pos] = left_node->keys.back(); // replace key
            left_node->keys.pop_back();
            left_node->key_count--;

            this->total_keys--;
            return 0;
        }

        // search right subtree
        auto right_node = n->children[pos + 1];

        for (;;)
        {
            if (right_node->is_leaf)
                break;

            right_node = right_node->children.front();
        }

        if (right_node->key_count >= this->md) // can grab
        {
            n->keys[pos] = right_node->keys.front(); // replace key

            for (int i = 0; i < right_node->key_count - 1; ++i)
                right_node->keys[i] = right_node->keys[i + 1]; // move backward

            right_node->key_count--;
            right_node->keys.pop_back();

            this->total_keys--;
            return 0;
        }

        // all fail. force replace with left.
        n->keys[pos] = left_node->keys.back(); // replace key
        left_node->keys.pop_back();
        left_node->key_count--;

        //PrintTree();

        auto result = Rebalance(left_node);
        if (result == 0)
        {
            this->total_keys--;
            return 0;
        }
        else
        {
            return result;
        }
    }
}

int BTree::Rebalance(std::shared_ptr<BTreeNode> n)
{
    //std::cout << "Rebalance " << std::endl;
    //PrintTree();
    // check left bro
    if (n->pnt_pos > 0) // has left bro
    {
        auto left_bro = n->pnt->children[n->pnt_pos - 1];
        //std::cout << "check left bro. key_count = "<< left_bro->key_count << std::endl;
        if (left_bro->key_count >= this->md)
        {
            // parent rotate down
            n->keys.push_back(0);
            n->key_count++;

            for (int i = n->key_count - 1; i >= 1; --i) // move all keys
                n->keys[i] = n->keys[i - 1];

            n->keys[0] = n->pnt->keys[n->pnt_pos - 1];

            if (!n->is_leaf)
            {
                n->children.push_back(nullptr);
                for (int i = n->key_count; i >= 1; --i) // move all children
                {
                    n->children[i] = n->children[i - 1];
                    n->children[i]->pnt_pos++;
                }

                // take left bro's subtree
                n->children[0] = left_bro->children.back();
                n->children[0]->pnt = n;
                n->children[0]->pnt_pos = 0;

                left_bro->children.pop_back();
            }

            n->pnt->keys[n->pnt_pos - 1] = left_bro->keys.back(); // left bro's last key rotate up

            // delete right bro's last key
            left_bro->keys.pop_back();
            left_bro->key_count--;

            return 0;
        }
    }

    // check right bro
    if (n->pnt_pos < n->pnt->key_count) // has right bro
    {
        auto right_bro = n->pnt->children[n->pnt_pos + 1];
        //std::cout << "check right bro. key_count = " << right_bro->key_count << std::endl;
        if (right_bro->key_count >= this->md)
        {
            n->keys.push_back(n->pnt->keys[n->pnt_pos]); // parent rotate down
            n->key_count++;

            if (!n->is_leaf)
            {
                // take right bro's subtree
                n->children.push_back(right_bro->children.front());
                n->children.back()->pnt_pos = n->key_count;
                n->children.back()->pnt = n;
            }

            n->pnt->keys[n->pnt_pos] = right_bro->keys.front(); // right bro's first key rotate up

            // delete right bro's first key
            for (int i = 0; i < right_bro->key_count - 1; ++i)
                right_bro->keys[i] = right_bro->keys[i + 1];

            if (!n->is_leaf)
            {
                for (int i = 0; i <= right_bro->key_count - 1; ++i)
                {
                    right_bro->children[i] = right_bro->children[i + 1];
                    right_bro->children[i]->pnt_pos--;
                }

                right_bro->children.pop_back();
            }

            right_bro->keys.pop_back();
            right_bro->key_count--;

            return 0;
        }
    }

    // all bro fail. do merge.

    // set left
    auto left = n;
    if (n->pnt_pos > 0) // has left bro
        left = n->pnt->children[n->pnt_pos - 1];

    auto right = left->pnt->children[left->pnt_pos + 1];
    //std:: cout<< "left key 0 " << left->keys[0] << " righ " << right->keys[0] << std::endl;

    // update right children pnt_pos
    if (!right->is_leaf)
    {
        for (int i = 0; i <= right->key_count; ++i)
        {
            right->children[i]->pnt_pos += left->key_count + 1;
            right->children[i]->pnt = left;
        }
    }

    left->keys.push_back(left->pnt->keys[left->pnt_pos]); // push parent key

    left->keys.insert(left->keys.end(), right->keys.begin(), right->keys.end()); // push back right keys

    if (!right->is_leaf)
        left->children.insert(left->children.end(), right->children.begin(), right->children.end()); // push back right children

    left->key_count += right->key_count + 1;

    // move parent key and children
    for (int i = left->pnt_pos; i < left->pnt->key_count - 1; ++i)
        left->pnt->keys[i] = left->pnt->keys[i + 1];

    for (int i = left->pnt_pos + 1; i <= left->pnt->key_count - 1; ++i)
    {
        left->pnt->children[i] = left->pnt->children[i + 1];
        left->pnt->children[i]->pnt_pos = i;
    }

    left->pnt->keys.pop_back();
    left->pnt->children.pop_back();
    left->pnt->key_count--;

    this->total_nodes--;

    if (left->pnt == this->root)
    {
        if (left->pnt->key_count > 0)
            return 0;

        // root empty
        this->root = left;
        this->height--;
        this->total_nodes--;
        return 0;
    }

    if (left->pnt->key_count >= this->md - 1)
        return 0;

    return Rebalance(left->pnt);
}

int BTree::Destroy(std::shared_ptr<BTreeNode> n)
{
    return 0;
}

int BTree::PrintInfo()
{
    std::cout << "Btree PrintInfo:" << std::endl;
    std::cout << "md = "<< this->md << std::endl;
    std::cout << "total_keys = " << this->total_keys << std::endl;
    std::cout << "total_nodes = " << this->total_nodes << std::endl;
    std::cout << "height = " << this->height << std::endl;
    return 0;
}

BTree.cpp

#include <iostream>
#include <fstream>
#include <chrono>
#include <cassert>
#include <memory>

#include "BTree.h"

int total_nodes, md, gap;

int test_case(std::shared_ptr<BTree> btree, int task, int answer, std::fstream &fs)
{
    // insert_all
    long long total_time = 0;
    int count = 0;
    int data = 0;
    for (;;)
    {
        fs >> data;
        if (data == gap)
            break;

        auto t1 = std::chrono::system_clock::now();
        int result = -1;

        switch (task)
        {
        case 0:
            result = btree->Insert(data);
            break;
        case 1:
            result = btree->Find(data);
            break;
        case 2:
            result = btree->Find(data);
            break;
        case 3:
            result = btree->Insert(data);
            break;
        case 4:
            //std::cout << "delete " << data << std::endl;
            //btree->PrintTree();
            result = btree->Delete(data);
            break;
        case 5:
            result = btree->Find(data);
            break;
        case 6:
            result = btree->Find(data);
            break;
        case 7:
            //std::cout << "delete " << data << std::endl;
            //btree->PrintTree();
            result = btree->Delete(data);
            break;
        case 8:
            answer = data;
            result = btree->TotalKeys();
            break;
        case 9:
            //std::cout << "delete " << data << std::endl;
            //btree->PrintTree();
            result = btree->Delete(data);
            break;
        case 10:
            answer = data;
            result = btree->TotalKeys();
            break;
        case 11:
            result = btree->Insert(data);
            break;
        case 12:
            answer = data;
            result = btree->TotalKeys();
            break;
        }

        if (answer != -1) // don't need to check
        {
            if (result != answer)
                std::cerr << "task " << task << " failed " << data << std::endl;
            assert(result == answer);
        }
        auto t2 = std::chrono::system_clock::now();

        auto nanoseconds = std::chrono::duration_cast<std::chrono::nanoseconds>(t2 - t1).count(); // microseconds nanoseconds
        total_time += nanoseconds;
        //std::cout << "milliseconds " << milliseconds << std::endl;
        count++;
    }

    switch (task)
    {
    case 0:
        std::cout << "insert all nodes ok avg time = " << total_time / count << " nanoseconds" << std::endl;
        break;
    case 1:
        std::cout << "find all good nodes ok avg time = " << total_time / count << " nanoseconds" << std::endl;
        break;
    case 2:
        std::cout << "find all bad nodes ok avg time = " << total_time / count << " nanoseconds" << std::endl;
        break;
    case 3:
        std::cout << "insert dup nodes ok avg time = " << total_time / count << " nanoseconds" << std::endl;
        break;
    case 4:
        std::cout << "delete nodes ok avg time = " << total_time / count << " nanoseconds" << std::endl;
        break;
    case 5:
        std::cout << "find deleted nodes ok avg time = " << total_time / count << " nanoseconds" << std::endl;
        break;
    case 6:
        std::cout << "find not deleted nodes ok avg time = " << total_time / count << " nanoseconds" << std::endl;
        break;
    case 7:
        std::cout << "deleted not exist nodes ok avg time = " << total_time / count << " nanoseconds" << std::endl;
        break;
    case 8:
        std::cout << "check size ok avg time = " << total_time / count << " nanoseconds" << std::endl;
        break;
    case 9:
        std::cout << "delete all ok avg time = " << total_time / count << " nanoseconds" << std::endl;
        break;
    case 10:
        std::cout << "check size ok avg time = " << total_time / count << " nanoseconds" << std::endl;
        break;
    case 11:
        std::cout << "insert all ok avg time = " << total_time / count << " nanoseconds" << std::endl;
        break;
    case 12:
        std::cout << "check size ok avg time = " << total_time / count << " nanoseconds" << std::endl;
        break;
    }

    return total_time / count;
}

int simple_test()
{
    //auto t0 = std::time(nullptr);
    std::fstream fs("btree_test_data_1.txt", std::fstream::in);
    if (!fs.is_open())
    {
        std::cout << "no test data\n";
        return 1;
    }

    fs >> total_nodes >>md  >> gap;

    std::cout << md <<" "<<total_nodes<<" "<< gap <<std::endl;

    auto btree = std::make_shared<BTree>(md);
    //btree->PrintInfo();

    auto test_0_result = test_case(btree, 0, 0, fs);

    //btree->PrintInfo();

    auto test_1_result = test_case(btree, 1, 1, fs);

    auto test_2_result = test_case(btree, 2, 0, fs);

    auto test_3_result = test_case(btree, 3, 1, fs);

    //btree->PrintTree();

    auto test_4_result = test_case(btree, 4, 0, fs);
    //btree->PrintTree();

    auto test_5_result = test_case(btree, 5, 0, fs);

    //btree->PrintTree();

    auto test_6_result = test_case(btree, 6, 1, fs);
    auto test_7_result = test_case(btree, 7, 1, fs);
    //btree->PrintTree();
    btree->PrintInfo();
    auto test_8_result = test_case(btree, 8, 0, fs);
    btree->PrintInfo();
    auto test_9_result = test_case(btree, 9, -1, fs);
    //btree->PrintTree();
    btree->PrintInfo();
    auto test_10_result = test_case(btree, 10, 0, fs);
    auto test_11_result = test_case(btree, 11, 0, fs);
    auto test_12_result = test_case(btree, 12, 0, fs);

    btree->PrintInfo();

    std::cout << "test_0_result avg time " << test_0_result << " nanoseconds" << std::endl
        << "test_1_result avg time " << test_1_result << " nanoseconds" << std::endl
        << "test_2_result avg time " << test_2_result << " nanoseconds" << std::endl
        << "test_3_result avg time " << test_3_result << " nanoseconds" << std::endl
        << "test_4_result avg time " << test_4_result << " nanoseconds" << std::endl
        << "test_5_result avg time " << test_5_result << " nanoseconds" << std::endl
        << "test_6_result avg time " << test_6_result << " nanoseconds" << std::endl
        << "test_7_result avg time " << test_7_result << " nanoseconds" << std::endl
        << "test_8_result avg time " << test_8_result << " nanoseconds" << std::endl
        << "test_9_result avg time " << test_9_result << " nanoseconds" << std::endl
        << "test_10_result avg time " << test_10_result << " nanoseconds" << std::endl
        << "test_11_result avg time " << test_11_result << " nanoseconds" << std::endl
        << "test_12_result avg time " << test_12_result << " nanoseconds" << std::endl;

    return 0;
}

int main()
{
    simple_test();

    return 0;
}

python生成测试数据

import random


TOTAL_SIZE = 100
MINIMUM_ORDER = 3
MAX_VALUE = 1000
FIND_FAIL_COUNT = 20
DELETE_OK_COUNT = 20

TOTAL_SIZE = 1000000
MINIMUM_ORDER = 20
MAX_VALUE = 10000000
FIND_FAIL_COUNT = 100000
DELETE_OK_COUNT = 100000

TOTAL_SIZE = 1000
MINIMUM_ORDER = 3
MAX_VALUE = 10000
FIND_FAIL_COUNT = 500
DELETE_OK_COUNT = 500


TOTAL_SIZE = 10000
MINIMUM_ORDER = 10
MAX_VALUE = 100000
FIND_FAIL_COUNT = 500
DELETE_OK_COUNT = 200


TOTAL_SIZE = 100000
MINIMUM_ORDER = 10
MAX_VALUE = 10000000
FIND_FAIL_COUNT = 500
DELETE_OK_COUNT = 200


GAP = -999999999

'''
TOTAL_SIZE
insert ok data
find ok data
find fail data
insert dup data
delete exist
find deleted
find not deleted
delete not exist
check size TOTAL_SIZE - DELETE_OK_COUNT
delete all
check size 0

'''

def gen_data():
    good_data_set = set()
    #find_ok_data_set = set()

    count = 0
    dup_data = set()

    delete_data_list = []
    no_delete_data_list = []

    with open("btree_test_data_2.txt", 'w') as f:
        f.write("%d\n%d\n%d\n" % (TOTAL_SIZE, MINIMUM_ORDER, GAP))

        while(True):
            data = random.randint(0, MAX_VALUE)
            if data not in good_data_set:
                f.write("%d\n" % data)
                good_data_set.add(data)
                count += 1

                if count >= TOTAL_SIZE:
                    f.write("%d\n" % GAP)#f.write("INSERT_OVER\n")
                    break
            else:
                dup_data.add(data)

        # find all ok
        good_data_list = list(good_data_set)
        random.shuffle(good_data_list)
        for data in good_data_list:
            f.write("%d\n" % data)

        f.write("%d\n" % GAP)#f.write("FIND_OK_OVER\n")

        # find all fail
        count = 0
        while (True):
            data = random.randint(0, MAX_VALUE)
            if data not in good_data_set:
                f.write("%d\n" % data)
                count += 1
                if count == FIND_FAIL_COUNT:
                    break

        f.write("%d\n" % GAP)#f.write("FIND_FAIL_OVER\n")

        # dup all
        random.shuffle(good_data_list)
        for data in good_data_list:
            f.write("%d\n" % data)

        f.write("%d\n" % GAP)#f.write("INSERT_DUP_OVER\n")

        # delete ok
        count = 0
        random.shuffle(good_data_list)
        delete_data_list = good_data_list[:DELETE_OK_COUNT]
        no_delete_data_list = good_data_list[DELETE_OK_COUNT:]
        for data in delete_data_list:
            f.write("%d\n" % data)

        f.write("%d\n" % GAP)  # f.write("INSERT_DUP_OVER\n")

        # find deleted
        count = 0
        random.shuffle(delete_data_list)
        for data in delete_data_list:
            f.write("%d\n" % data)

        f.write("%d\n" % GAP)  # f.write("INSERT_DUP_OVER\n")

        # find not deleted
        for data in no_delete_data_list:
            f.write("%d\n" % data)

        f.write("%d\n" % GAP)  # f.write("INSERT_DUP_OVER\n")

        # delete not exist
        count = 0
        while (True):
            data = random.randint(0, MAX_VALUE * 10)
            if data not in good_data_set:
                f.write("%d\n" % data)
                count += 1
                if count == DELETE_OK_COUNT:
                    break

        f.write("%d\n" % GAP)  # f.write("FIND_FAIL_OVER\n")

        f.write("%d\n" % (TOTAL_SIZE - DELETE_OK_COUNT))
        f.write("%d\n" % GAP)

        # delete all
        random.shuffle(good_data_list)
        for data in good_data_list:
            f.write("%d\n" % data)

        f.write("%d\n" % GAP)

        # check size
        f.write("%d\n" % 0)
        f.write("%d\n" % GAP)

        # insert all
        random.shuffle(good_data_list)
        for data in good_data_list:
            f.write("%d\n" % data)
        f.write("%d\n" % GAP)
        # check size
        f.write("%d\n" % TOTAL_SIZE)
        f.write("%d\n" % GAP)

gen_data()