65.9K
CodeProject 正在变化。 阅读更多。
Home

B 树数据库类的实现

_oti
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.86/5 (37投票s)

2004 年 6 月 14 日

11分钟阅读

viewsIcon

545259

downloadIcon

5258

一篇关于在 C++ 中实现 B 树的文章和源代码。

引言

此源代码（作为演示项目的一部分）创建并使用 BTree 数据库。它实现了以下功能：

  • 创建数据库
  • 插入/更新记录
  • 删除记录
  • 搜索键（精确匹配或某种通配符）
  • 遍历
  • 顺序向前和向后记录访问
  • 用户指定的固定大小记录和固定大小键
  • 自定义比较和遍历回调

背景

很久以前，我开始开发一个系统，该系统可以允许人们对（澳大利亚）股票市场走势进行精美、简单且用户友好的图表绘制。显然，该系统的客户端的大部分将是在本地机器上存储股票走势。人们需要能够查看他们的图表，而不必每次打开窗口时都下载大量数据。从编程角度来看，如果这些走势可以按日期顺序检索，那将是有意义的，因为在图表窗口中绘制股票走势需要按日期顺序呈现数据。我也需要能够快速检索它们。请记住，通过下载附带的数据包，一些证券可以追溯到 1980 年。

经过一番折腾，我最终决定编写自己可以使用的数据库功能（非 GPL 授权，非极其昂贵）。有关此过程的完整讨论，请参阅“兴趣点”部分。

BTreeDB 的内容和结构

在深入了解树本身之前，让我们先看看是什么构成了一棵树。

智能指针

如果您不了解智能指针，现在是时候了解它们了。查看 这里 了解我用作智能指针基础的文章。它们的作用是允许您复制指针，管理自己的引用计数，并确保在对象的最后一个引用被释放或超出作用域时删除对象。

数据库内部对象大量使用智能指针，因为……嗯，它实在太方便了。

DbObj 类

DbObj 是一个通用的数据块。要创建一个，您需要调用构造函数，提供一个指向数据的指针和数据大小。还有一些其他构造函数允许您创建各种类型的 DbObj，而无需担心大小。这些包括 std::string、数字和其他 DbObj 的构造函数。请注意，这些对象会复制您的数据，因此您不能期望创建 DbObj，然后更改原始数据，并期望更改会反映在 DbObj 中。还要注意，DbObj 不包含有关存储的数据类型的信息。

代码处理指向 DbObj 对象的智能指针。您创建 DbObj，将它们传递给 BTreeDB，然后忘记它们。或者，从 BTreeDB 中取回一个，而不必担心显式释放它。引用计数基础结构会处理好这一切。

DbObj 对象用于指定要插入 BTreeDB 的数据，以及用于在 BTreeDB 中查找记录的键。

在下面的所有示例代码中，我使用的是由以下部分组成的记录结构：

const size_t keyLen = 12;
const size_t dataLen = 28;

struct SampleKey
{
    unsigned char key[keyLen];
};
struct SampleData
{
    unsigned char data[dataLen];
};
struct SampleRecord
{
    SampleKey key;
    SampleData data;
};

要创建包含此类对象的 DbObj，您需要执行以下操作：

SampleRecord sr;
memset(&sr.key, 'K', keyLen);
memset(&sr.data, 'D', dataLen);

DbObjPtr pRec = new DbObj(&sr, sizeof(SampleRecord));

TreeNode 类

B 树包含一个多级分层树节点集合（即一棵树）。这些节点包含一系列记录以及指向子节点的引用。节点中的记录如上所述存储为 DbObj，而子节点存储为指向 TreeNode 对象的智能指针列表。

这些是将被读取和写入磁盘的块。它们不会被加载，直到实际需要为止。

使用 BTreeDB

创建 BTreeDB

要创建 BTreeDB 对象，请调用构造函数（废话！）。

BTreeDB db(fileName, sizeof(SampleRecord), sizeof(SampleKey), minDegree);

第一个参数 (fileName) 是一个 const char*，指向包含文件名缓冲区的指针。如果文件不存在，它将被创建。如果文件已存在，它将被用作包含有效数据的数据库文件。请注意，构造函数不会打开文件。它只是初始化数据成员。第二个参数是记录大小（以字节为单位），用于存储在数据库中。第三个参数允许您指定这些字节中有多少将被解释为键。第四个参数是树的最小度，通常在文本中称为 t。树节点最多可以容纳 2t - 1 个键，但不能少于 t 个。

上面没有显示构造函数的第五个参数。如果您的记录在排序时需要除了二进制比较之外的其他比较方式，您可以提供自己的比较函数。默认比较是使用两个被比较数据对象的第一个 keyLength 字节进行简单的 memcmp。

打开 BTreeDB

db.open()

如果在构造函数中提供的文件不存在，则会创建该文件并将其初始化为处理构造函数中提供的记录和键的大小。如果文件已存在，则会将提供的值与文件中已有的值进行比较，如果存在差异，数据库将不会打开。

如果由于任何原因未能打开数据库，此方法将返回 false。

失败原因包括：

  • 数据库文件被另一个进程锁定。
  • 构造函数中未提供 size 和 minDegree 参数 **且** 文件尚不存在。
  • 如果需要创建文件但无法创建。
  • 如果文件已存在，则无法从文件中读取头信息。

是的，我本可以使 open 函数返回一个错误代码，但我没有。也许以后吧。

将数据插入 BTreeDB

这只是创建您想插入的 DbObj，然后插入它们。

for (int i = 0; i < iterLimit; i++)
{
    SampleRecord sr;
    makeRecord(&sr);    // This just fills in the sample record
    
    DbObjPtr pObj = new DbObj(sr, sizeof(SampleRecord));
    db.put(pObj);
}

您必须确保提供正确大小的记录。如果不是这种情况，put 方法将返回 false。

此方法也用于更新现有记录。请注意，BTreeDB 不允许您插入具有相同键的多个记录。如果您“put”任何与现有记录具有相同键的记录，现有记录将被覆盖。

从 BTreeDB 检索数据

创建一个包含键的 DbObj，然后请求记录。

SampleKey sk;
memset(&sk, 'K', sizeof(SampleKey));

DbObjPtr pKey = new DbObj(&sk, sizeof(SampleKey));
DbObjPtr pRec;
if (db.get(pKey, pRec))
{
    SampleRecord sr;
    assert(pRec->getSize() == sizeof(SampleRecord));
    memcpy(&sr, pRec->getData(), pRec->getSize());
}

从 BTreeDB 中删除数据

花了很长时间才将此功能弄对，但使用它却相当简单。

SampleKey sk;
memset(&sk, 'K', sizeof(SampleKey));

DbObjPtr pKey = new DbObj(&sk, sizeof(SampleKey));
db.del(pKey);

对 BTreeDB 的其他操作

代码中有关于如何遍历 BTreeDB、如何执行“like”搜索（其中搜索键小于实际记录键大小）、在树中向前和向后移动以及一些可能对我来说独一无二的其他内容的示例。

BTreeDB 包装器

我使用包装器来为给定的数据库提供结构。（我不知道在哪里找到的 Singleton 类……[需要在此处插入链接]）。

class HistoryDB
{
    static const int _dbMinDegree = 49;
    friend class Singleton<HistoryDB>;

public:
    struct HistoryKey
    {
        byte exchange;
        char security[10];
        ushort moveDate;
        byte padding[3];
    };

    struct HistoryItem
    {
        int openPrice; // Opening price in currency units 
                       // (implied by Exchange context)
        int highPrice; // High price in currency units 
                       // (implied by Exchange context)
        int lowPrice;  // Low price in currency units 
                       // (implied by Exchange context)
        int closePrice; // Closing price in currency units 
                        // (implied by Exchange context)
        llong tradeVolume; // Volume of trades for the trading day
        byte intraday;   // 0 = this is an EOD value, 
                         // 1 = intraday progressive value.
        byte padding[7];
    };

    struct HistoryRecord
    {
        struct HistoryKey key;
        struct HistoryItem item;
    };

private:
    static int _compareHR(const DbObjPtr& pObj1, 
                          const DbObjPtr& pObj2)
    {
        HistoryKey* k1 = (HistoryKey*)pObj1->getData();
        HistoryKey* k2 = (HistoryKey*)pObj2->getData();
        int ret = k1->exchange != k2->exchange;
        if (ret == 0)
        {
            ret = strcmp(k1->security, k2->security);
            if (ret == 0)
            {
                ret = k1->moveDate - k2->moveDate;
            }
        }
        return ret;
    }

private:
    HistoryDB(void)
    {
        GlobalData& gd = GlobalDataS::instance();
        string fileName = gd.getDataDir() + "history.db";
        _db = new BTreeDB(fileName,
            sizeof(HistoryRecord),
            sizeof(HistoryKey),
            _dbMinDegree,
            _compareHR);
        if (!_db->open())
        {
            _db = (BTreeDB*)0;
        }
    }

public:
    BTreeDBPtr& getDB() { return _db; }

private:
    BTreeDBPtr _db;
};
typedef Singleton<HistoryDB> HistoryDBS;

给定上面的类，我可以这样做：

HistoryDB& hdb = HistoryDBS::instance();
BTreeDBPtr pdb = hdb.getDB();
HistoryDB::HistoryRecord hr;
DBOBJVECTOR dbMoves;

memset(&hr, 0, sizeof(hr));
strcpy(hr.key.security, stockCode);
DbObjPtr pKey = new DbObj(&hr, sizeof(hr));
NodeKeyLocn locn = pdb->search(pKey);
if ((TreeNode*)locn.first != 0)
{
    DbObjPtr pRec;
    while (pdb->seq(locn, pRec))
    {
        memcpy(&hr, pRec->getData(), 
               sizeof(HistoryDB::HistoryRecord));
        if (0 != memcmp(pRec->getData(),
            pKey->getData(),
            sizeof(hr.key.exchange) + sizeof(hr.key.security)))
        {
            break;
        }
        dbMoves.push_back(pRec);
    }
}

注意事项

这不是线程安全的。我使用我自己的互斥锁来保护应用程序中对数据库的访问。

您需要注意何时打开和关闭数据库，以及何时将它们刷新到磁盘。有些方面我还没有完全探索过，但我知道我应该比现在更频繁地释放内存（TreeNodes）。如果这样做，您最终会发现整个数据库都存储在内存中。虽然这对小型数据库的性能非常好，但可能不适合大型数据库。

目前，它适合我正在做的事情。

关注点

我第一次尝试实现一个数据库只是为每个证券设置一个文件，数据按顺序存储。对于 ANZ，有一个名为 ANZ.fdb 的文件；对于 CBA，有一个名为 CBA.fdb 的文件，依此类推。这还可以，因为 ASX（澳大利亚证券交易所）上的证券少于两千种。随着项目的增长，我开始包含期权，我不得不将它们放入以基础证券命名的子目录中。这开始看起来 *非常* 丑陋。我曾设想，在存储认股权证和股票的盘中波动时，我还会遇到更多麻烦。

我寻找过替代方案。 MySQL 有一个嵌入式数据库引擎，速度非常快，但对于免版税分发许可证来说，成本会非常高，或者需要我将整个项目开源。嗯……暂时不行。 Sleepcat 有 Berkeley DB，这是一个非常快速高效的嵌入式数据库引擎，所以我看了一下。同样，成本很高，或者需要开源。他们确实有一个旧版本（1.8.5），它是在 BSD 分发许可证下发布的，完全免费。我对此进行了一些研究，但正如一些网站所指出的，它存在一些众所周知的错误。我对此项目了解不多，无法修复它们。仅供参考：如果您需要嵌入式数据库，并且符合开源标准（或个人使用，等等），请选择这些软件包 :-)

所以我被卡住了。我不想在用户的文件系统中四处散布一大堆文件，但我希望能够随着时间的推移添加许多记录，并快速检索它们。我需要某种数据库软件包，找不到，所以最终我决定自己动手。好吧。那么从哪里开始呢？回到我上大学的日子，以及二年级的《数据结构与算法》课程。这门课的教材是 Cormen、Leiserson 和 Rivest 的优秀著作《算法导论》第二版，MIT 出版社，马萨诸塞州，1990 年。虽然当时我们没有学习 B 树，但我记得后来曾试图实现一个 B 树，以一种失败的方式进入娱乐业。长话短说……别问。但是这次，我决心要成功。

哦……为什么要使用 B 树？嗯，它们用起来很方便，因为它们允许将大量数据存储在磁盘上，通过键进行索引，记录的访问时间大约是 O(log n)，其中 n 是树中的节点数。有很多地方可以找到更多关于 B 树的信息。我不倾向于在此处复制大段文本，但如果您有兴趣，可以查看 这里。它包含了 Cormen、Leiserson 和 Rivest 关于创建、搜索和插入记录的基本算法。

回到手头的任务，我知道删除会是个问题，因为 *没人* 发布 B 树中删除键的伪代码。它似乎比其他操作更复杂，通常“留给读者练习”。真是的。所以我研究了其他教科书，并在网上搜索。最终，我找到了一篇题为“在 B+-树中实现删除”的文章，作者是斯坦福大学的 Jan Jannick。引用摘要：“有关于搜索和插入键的已发布算法和伪代码，但删除由于其更大的复杂性和被认为不太重要而被完全忽略或留给读者练习。为了纠正这种情况，我们提供了一个文档齐全的流程图、算法和删除的伪代码，以及它们与搜索和插入算法的关系，以及对一个用 C 编程语言编写的免费、完整的 B+-树库的引用。”太好了！所以我下载了论文中引用的代码（您可以从 这里 开始获取）。但是，C 代码在 VS7 中无法编译，C++ 代码在几次插入后就崩溃了。糟糕。

所以，我构建了创建、插入和搜索代码等，使用了教科书的伪代码。由于无法在别处找到任何删除的伪代码，我决定必须咬紧牙关，根据叙述编写代码。经过很长时间，一切都成功了。我决定没有人应该再经历这一切，所以我将代码公开分发。这可能会让许多大学讲师感到沮丧，因为现在有实际执行这个该死的删除操作的代码了，但不知怎的……我不在乎。我胜利了！

附录：并非一切都奏效。很接近，但并非完美。删除仍然存在问题。测试代码中有三种不同的删除顺序：普通字母顺序、反字母顺序，以及某种其他方式。“某种其他方式”有时会导致并非所有项目都被删除。我现在没有时间去研究这个问题。也许，当我的产品能让我和我的家人过上我们想要的生活时……

历史

  • 2004 年 6 月 9 日：首次发布。
  • 2004 年 7 月 12 日：在演示中包含时间戳，修复了反向迭代代码。
  • 2006 年 6 月 28 日：包含 AdamWynne 和 steradrian 提出的修复。
© . All rights reserved.