如何实现简单的关系数据库？

Question

请注意,这个问题是关于C++ 只是,我不想使用现有的数据库库,我也没有寻求一个通用的解决方案,以"数据库在C++".我有一个特定的问题,并且遵循以下问题的最有效(在时间,空间和最佳实践方面)解决方案.

假设我有一个系列的书,通过描述Id,ISBN,Author,和Name.该Name柱将其涉及作者的一个单独的表,包含的列的ID Id,Surname,First Name.我希望能够通过名称和作者进行有效搜索.我将如何构建这个,以及我将使用哪些容器？

在SO和其他地方已经多次讨论过这个主题,但是从来没有专门针对C++或不使用现有库的实现的答案.

天真的解决方案只是创建两个单独的类:Author和Book:

class Book
{
public:
  int id;
  std::string isbn;
  Author* author;
  std::string name;
};

class Author
{
public:
  int id;
  std::string surname;
  std::string givenName;
};

然后我可以创建Book和Author(指针)的向量.但是我如何有效地索引这些？假设我想通过它的ISBN找到一本书; 我怎样才能在恒定或至少对数时间内做到这一点？这可能吗？这种问题有标准做法吗？

Answer 1

首先，标准容器不支持通过多个键进行索引——每个容器仅支持单个键。这可以是一个复合键，因此，如果您有三本书，作者不同，标题相同，您可以同时指定标题和作者，以仅查找其中一本。然而，没有一个标准容器支持按标题或作者单独搜索。

Boost Multi-Index库相当直接地支持每个项目多个键。多索引教程有创建外键的示例，就像您有兴趣使用的一样。

多索引支持基于（红黑）树和基于哈希的索引。像往常一样，您可以在两者之间进行权衡 - 散列索引通常可以更快地查找单个项目，但基于树的索引支持不等式，因此如果您想要搜索范围之类的内容（例如， “姓氏从‘C’到‘L’的作者的书籍”）。