SQL 结构与 C++ STL 映射

Question

我刚刚在学校完成了数据结构和算法 (cpp) 的课程，我对现实世界中的数据库感兴趣……特别是 SQL。

所以我的问题是 SQL 和例如 c++ stl std::multimap 之间有什么区别？SQL 更快吗？或者我可以使用 C++ STL 制作同样快（时间复杂度明智）的自制 SQL 吗？

谢谢！（对不起，我是在我的课程范围之外编程的新手）

Answer 1

明显的区别是SQL是一种与数据库交互的查询语言，而STL是库（按照惯例，STL 也用于指代标准 C++ 库的某个子集）。因此，这些是苹果和橙子。

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

1. STL 容器突变不需要是原子的：当从其中一个突变函数中抛出异常时，容器可能变得不可用，即 STL 容器只需要满足基本的异常保证。
2. 如前所述，[成功] 突变会产生一致的状态。
3. STL 容器目前不能被改变和读取，即没有隔离的概念。如果您想在并发环境中访问 STL 容器，您需要确保在容器发生变异时没有其他访问器（尽管没有变异器，但您可以拥有尽可能多的并发读取器）。
4. STL容器有持久性的概念，而持久性可能被认为是数据库的核心特性（好吧，所有的ACID特性都可以被认为是核心数据库特性）。

数据库内部肯定会使用一些数据结构和算法来提供 ACID 特性。这是一个 STL 可能进入的领域，尽管主要是它的关键优势，即算法不是真正的“算法”，而是“特定问题的求解器”：STL 是有效算法库的基础，适用于任意数据结构（嗯，这就是目标 -我认为还没有实现）。遗憾的是，数据结构的重要领域并没有得到适当的涵盖。特别是关于树上的数据库算法，尤其是b 树往往很重要，但 STL 根本没有涵盖。

STL 容器std::multimap<...>确实包含一棵树（通常是红/黑树，但不是强制性的），但它与这种特定的内存表示相关联。无法将用于实现此特定数据结构的算法应用于某些合适的持久表示。此外，std::multimap<...>仍然只使用一个键（多是指允许具有相同的键的多个元件，不具有多个键），而数据库通常需要多个查找机制（指数是基于一个执行查询时使用的查询计划用于每个查询。

你有多个问题，有趣的一个（在我看来）是这样的：“......或者我可以使用 C++ STL 制作同样快（时间复杂度明智）的自制 SQL 吗？”

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

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

请注意，时间复杂度往往有助于指导对不同方法的快速评估。然而，在实践中，常数因素往往很重要，通常时间复杂度较低的算法表现更好。典型的例子是快速排序，其性能优于“上级”算法（例如堆排序或归并为典型输入）（尽管在实践中实际上内省排序使用哪个是快速排序，堆排序的混合体，和插入排序，使用相结合的这些强度相应的算法在所有输入上都表现良好）。顺便说一句，要获得算法的说明，您可能想观看匈牙利排序舞者.