# 基于C++14的B-树

**Repository Path**: lin-xi-269/b-tree-cpp14

## Basic Information

- **Project Name**: 基于C++14的B-树
- **Description**: No description available
- **Primary Language**: C++
- **License**: GPL-3.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2022-02-22
- **Last Updated**: 2023-05-18

## Categories & Tags

**Categories**: Uncategorized

**Tags**: B-树

## README

此project是本人为了为了更加深刻地理解B-树、B+树、B*树、以及锻炼modern c++ 能力所实现的一个template B-树。采用的c++标准是C++14。

此B-树的实现具有以下几点优势：

1. 内部的指针管理全是使用的unique_ptr。
2. 面向modern c++编程，B-树的实现没有使用一处new和delete，直接从根源上杜绝了常见的内存泄漏
3. 设计的key是完全适应移动语义的，也就意味着，如果你具现化的class设计的是可以移动的，那么在插入的时候是不需要承担copy的成本的。
4. 因为实现采用的template，所以只要传入的类是重载了==和>的，那么都可以方便的进行扩展。比如可以用[key, data]具现化一个B树，或者是只用key具现化一个索引集合，或者是具现化为B+树（修改一下外部结点）、B*树（添加一个兄弟指针），都是可以的
5. 每一个结点key，child是通过Vector（final的）存储的，而Vector的设计是直接private inherit STL的，开放了常用的STL::vector的接口，方便使用，并且效率也高。



一些设计上的不足：

虽然我内部都是用的unique_ptr存储，但是我在一开始思考insert的返回值的时候，我觉得返回unique_ptr&不安全，所以返回了原始指针，但是现在做完了整个设计，我发现直接返回const unique_ptr& 或许是比原始指针更加好的选择。





### 测试

我使用了两种测试

1. 针对B-树是否正确实现的单元测试，主要由/UniPrint/print.h（由邓俊辉老师所写，我针对性地做了一些修改）中的printBTree提供，我多次检测了多种阶数的B树和多种阶码（{3,1000}，{3, 10000},{10,10000},{200,10000} ）都得到了正确的结果
2. 针对内存泄漏做了测试，主要用的是valgrind ,以及比较长时间的运行程序也没有问题。





### 代码和注释

我遵循的代码风格是类似于Google的，不过没有完全遵循，因为在我这行数下，我感觉缩进为4个空格会更加好看。

另外我大部分代码都使用了doxygen注释，也生成了doxygen文档在BTree/html中可以看到一些class或者函数的关系及功能。



B-树

B-树的定义可参考维基百科：[B树 - 维基百科，自由的百科全书 (wikipedia.org)](https://zh.wikipedia.org/wiki/B树)