c++ - SQL结构与C++ STL映射

Question

我刚刚在学校完成了一门有关数据结构和算法(cpp)的类(class)，并且对现实世界中的数据库基础特别是SQL感兴趣。

所以我的问题是SQL与例如c++ STL std::multimap之间有什么区别？ SQL更快吗？还是可以使用C++ STL制作同样快(在时间复杂度方面)的自制SQL？

谢谢!
(对不起，我是在类界限之外进行编程的新手)

Answer 1

明显的区别是SQL是一种查询语言，可以与数据库进行交互，而STL是一种库(通常，STL也用于引用standard C++ library的某个子集)。因此，这些是苹果和橙子。

SQL实际上需要一套指定数据库系统各个部分的标准。为了使数据库系统有用，需要满足某些特征(ACID。即使仅查看这些特征，也没有要求STL容器满足它们的要求。我认为对于STL容器，甚至只需要一致性即可:

不需要STL容器突变是原子的:当从一个变异函数中引发异常时，该容器可能变得不可用，即仅要求STL容器满足basic exception guarantee。

如前所述，[成功]突变产生一致状态。

STL容器当前无法变异和读取，即没有隔离的概念。如果要在并发环境中访问STL容器，则需要确保在对容器进行突变时没有其他访问器(但是，在没有mutator的情况下，您可以具有多个并发读取器)。

STL容器具有持久性的概念，尽管它可能被认为是数据库的持久性核心特征(好吧，所有ACID功能都可以被视为核心数据库特征)。

数据库内部肯定会使用某些数据结构和算法来提供ACID功能。这是STL可能进入的一个 Realm ，尽管主要具有其主要优势，即，算法并不是真正的“algorithms”，而是“特定问题的解决者”:STL是高效算法库的基础，适用于任意数据结构(好吧，这就是目标-I don't think it is, yet, achieved)。遗憾的是，数据结构的重要 Realm 并未得到适当覆盖。特别是对于trees上的数据库算法，尤其是b-trees往往很重要，但STL根本没有涵盖。

STL容器std::multimap<...>确实包含一棵树(通常是red/black-tree，但这不是强制性的)，但是它与该特定的内存表示形式相关。无法将用于实现此特定数据结构的算法应用于某些合适的持久性表示形式。同样，std::multimap<...>仍然仅使用一个键(multi表示允许具有相同键的多个元素，而不是具有多个键)，而数据库通常需要多种查找机制(indices，当执行基于query plan的查询以用于每个查询。

您有多个问题，有趣的是(我认为):“...还是我可以使用c++ STL进行同样快速(在时间复杂度方面)的自制SQL？”

在STL涵盖所有算法的理想世界中，可以的，您可以基于STL算法为数据库创建查询评估器。您甚至可以使用某些STL容器作为辅助数据结构，尽管数据库中的主要数据结构已在持久性存储中正确表示。要创建一个实际的数据库，您还需要一些东西来将查询转换为一个好的查询计划，然后可以执行该计划。

当然，如果您真正需要的只是通过程序中读取的数据结构中的某个键进行某些查找，则您不需要完整的数据库，并且使用合适的STL容器查找可能更快。

注意，time complexity往往有助于指导对不同方法的快速评估。但是，在实践中，恒定因素往往很重要，时间复杂度较低的算法通常表现更好。典范示例quicksort优于典型输入的“高级”算法(例如heapsort或mergesort)(尽管实际上introsort是快速排序，堆排序的混合体，并且insertion-sort结合了这些算法的强度)在所有输入上表现良好)。顺便说一句，要说明算法，您可能需要观看Hungarian Sort Dancers。