B+树性能测试(C++实现)

栏目: C++ · 发布时间: 5年前

内容简介:文章主要是对我自己实现的B+树的各项指标测试结果展示。B+树的CRUD具体算法文本未涉及,后续可能会补充。引自

文章主要是对我自己实现的B+树的各项指标测试结果展示。B+树的CRUD具体算法文本未涉及,后续可能会补充。

项目地址

github.com/SirLYC/BPTr…

B+树简介

引自 维基百科

B+ 树是一种树数据结构,通常用于数据库和操作系统的文件系统中。B+ 树的特点是能够保持数据稳定有序,其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入,这与二叉树恰好相反。

B+树结构

B+树有一个重要的参数叫 (m),决定了一颗B+树每一个节点存储关键子的个数。

每一个节点都会按顺序存储一组关键字,对于非根节点,其关键字树s >= (m + 1) /2。对于叶子节点,其结构中存储指向值的指针,与关键字对应,同时还有一个next指针,指向下一个兄弟叶子节点,因此找到最左叶子节点后可以按关键字顺序遍历;对于非叶子节点,存有s个指向子节点的指针。

B+树通过插入时分裂,删除时向兄弟节点借关键字或合并兄弟节点实现平衡,所有的叶子节点都在同一层。查询、插入、删除效率都是 Log(N)

实现的public API

template<typename K, typename V>
class BPTree {
private:
    ...

public:
    // constructor and destructors
    ...

    /**
     * deserialize from a file
     */
    static BPTree<K, V> deserialize(const std::string &path);

    static BPTree<K, V> deserialize(const std::string &path, comparator<K> comp);

    void put(const K &key, const V &value);

    void remove(K &key);

    /**
     * @return NULL if not exists else a pointer to the value
     */
    V *get(const K &key);

    bool containsKey(const K &key);

    int getOrder();

    int getSize();

    /**
     * iterate order by key
     * @param func call func(key, value) for each. func returns true means iteration ends
     */
    void foreach(biApply<K, V> func);

    void foreachReverse(biApply<K, V> func);

    void foreachIndex(biApplyIndex<K, V> func);

    void foreachIndexReverse(biApplyIndex<K, V> func);

    void serialize(std::string &path);

    /**
     * clear the tree
     * note that all values allocated will be freed
     */
    void clear();
};
复制代码

Tips:为了兼容自定义类别,需要传入比较大小的函数指针,或实现相应的>、=、<等运算符;

重要数据结构

Node:B+树的索引节点

主要数据结构如下:

struct Node {
    // parent
    // if root, parentPtr == NULL
    Node *parentPtr = NULL;
    // flag
    bool leaf;
    List<K> keys;
    /*-------leaf--------*/
    Node *previous = NULL;
    Node *next = NULL;
    List<V> values;
    /*-------index-------*/
    List<Node *> childNodePtrs;
    // for init
    int initCap;
    // constructor
    ...
};
复制代码

List<T>:使用定长数组实现的List,比起std::vector<T>功能更简单,效率更高;内存会在移除一定数量元素后减小。

序列化

  • 文件后缀为bpt
  • 头部格式:
偏移(byte) 大小(byte) 内容
0 4 LYC\0 头部标识
4 4 order,int类型,B+树的阶
8 4 initCap,int类型,每个节点预分配大小
12 4 size,int类型,元素个数
  • 如果size不为0,头部结束后就是根节点,节点有同一的格式,节点前面通用格式:
偏移(相对于节点起始,byte) 大小(byte) 内容
0 4 leaf,int类型,标识节点是否为叶子节点
4 4 sizeofK,int类型,key类型占字节数
8 4 kSize,int类型,该节点拥有的关键字数量
12 kSize * sizeofK 按顺序存储关键字
  • 对于叶子节点
偏移(相对于节点起始,byte) 大小(byte) 内容
12 + kSize * sizeofK 4 sizeofV,int类型,value类型占字节数
16 + kSize * sizeofK kSize*sizeofK 按顺序存储值
  • 对于非叶子节点
偏移(相对于节点起始,byte) 大小(byte) 内容
12 + kSize * sizeofK kSize * 8 long类型,按顺序存储字节点在文件中的偏移

实现要点

  • 最初的实现是使用vector,测下来性能不是特别理想;
  • 基于节点内关键字有序的特点,查找时使用二分查找;
  • 存储子节点应该存储指向节点的指针。因为涉及分裂、合并操作,需要复制列表,如果存储的是结构,复制会造成递归复制,效率低,且不易控制内存;
  • 因为 root 节点没有最少关键字限制,在删除节点操作完成后,需要检查一下 root 子节点数量,如果为1,直接将 root 的字节点设置为 root ,否则删除子节点后可能会造成 root 的关键字、子节点丢失。
  • 每一次插入、删除节点最后一个关键字后需要向上更新parent。
  • 分裂、合并操作时对于叶子节点next和previous指针要更新。

测试

测试环境:

B+树性能测试(C++实现)

文件 main.cpp 有如下宏,1表示开启测试:

// 测试List性能(和vector对比)
#define TEST_LIST 0
// 测试B+树功能正确性
#define TEST_FUNC 0
// 测试B+树的速度(增删查改)
#define TEST_SPEED 0
// 测试B+树的堆使用及内存泄漏(build后使用 工具 测试)
#define TEST_MEM 0
// 测试B+树的序列化与反序列化
#define TEST_SERIAL 0
复制代码

List测试

  • 数据量:10^5
  • 增、删数据,断言对应位置是否如预期(功能测试)
  • 尾部插入测试(预分配和不预分配)
  • 头部插入测试
  • 头删除测试
  • 尾删除测试
  • rangeRemove测试

测试运行结果:

B+树性能测试(C++实现)

表格:

List(ms) vector(ms)
尾部插入 1.506 4.724
尾部插入(预分配空间) 1.201 2.765
头部插入 834.804 906.981
移除一半元素(头部) 619.493 805.379
移除一半元素(尾部) 1.444 7.523
rangeRemove(一半) 0.065 0.558

柱状图:

B+树性能测试(C++实现)

B+树功能测试

  • 数据量:10^5
  • 数据插入后断言插入数据存在
  • 去除一半数据,断言去除数据不存在,未去除数据存在
  • 重新插入所有数据,断言所有数据都存在(测试删除是否破坏结构)
  • clear()后断言之前数据都不存在
  • 插入全部数据后,测试遍历方法(key顺序测试)

速度测试

  • 数据量:10^8、10^7、10^6
  • B+树阶为 log(TEST_SIZE)^2
  • 循环插入数据
  • 循环访问所有数据
  • 循环移除数据

测试运行结果:

B+树性能测试(C++实现)

表格:

bp tree(ms) stl map(ms)
插入(10^8) 192808.064 325621.333
访问(10^8) 163102.022 280150.403
移除(10^8) 213982.406 366576.836
插入(10^7) 11825.821 22213.139
访问(10^7) 10190.870 18137.073
移除(10^7) 15130.015 22133.154
插入(10^6) 1057.291 1624.615
访问(10^6) 888.186 1155.504
移除(10^6) 1099.584 1495.433

柱状图:

B+树性能测试(C++实现)

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

算法图解

算法图解

[美] Aditya Bhargava / 袁国忠 / 人民邮电出版社 / 2017-3 / 49.00元

本书示例丰富,图文并茂,以让人容易理解的方式阐释了算法,旨在帮助程序员在日常项目中更好地发挥算法的能量。书中的前三章将帮助你打下基础,带你学习二分查找、大O表示法、两种基本的数据结构以及递归等。余下的篇幅将主要介绍应用广泛的算法,具体内容包括:面对具体问题时的解决技巧,比如,何时采用贪婪算法或动态规划;散列表的应用;图算法;K最近邻算法。一起来看看 《算法图解》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

html转js在线工具
html转js在线工具

html转js在线工具