查询数据库的算法是什么？

Question

大家好，我目前正在研究搜索算法优化。

目前，我正在研究数据库。

在支持SQL的数据库中。

我可以为特定表编写查询。

1. 从Table1选择Number where Name =“Test”;
2. 从Table1选择* where Name =“Test”;

1是从Table1中搜索Name为Test的Number值，2是搜索所有列中的Name为Test的值。

我理解此函数的概念，但我想学习的是搜索的方法是什么？

它只是简单的线性搜索，从第一个索引到第n个索引，只要条件为真，它就会取出，因此具有O（n）速度，还是它具有加速其过程的独特算法？

- Treize

---

很可能MySQL（InnoDB）使用B树来优化搜索查询。 - nullpotent

Answer 1

如果没有索引，那么是进行线性搜索。

但是，当您将一列或多列指定为键时，数据库通常使用B Tree索引。这些是特殊的数据结构格式，经过专门调整（高B树分支因子），以在磁盘硬件上表现良好，其中最耗时的因素是寻道操作（磁头必须移动到文件的不同部分）。

您可以将索引视为列中值的排序/结构化副本。如果快速确定正在搜索的值是否在索引中，则可以快速找到它。如果找到了它，那么它还会找到一个指针，该指针指向主数据文件中相应行的正确位置（因此它可以去读取行中的其他列）。有时，多列索引包含查询请求的所有数据，然后它就不需要跳回主文件，它只需读取所找到的内容，然后完成任务。

还有其他类型的索引，但我想您已经明白了-重复数据并以便于搜索的方式排列它们。

对于大型数据库，索引使得查询的完成时间从可能需要几天缩短至等待几秒钟的差异。

顺便提一下，B树并不是一个简单易懂的数据结构，遍历算法也很复杂。此外，遍历甚至比大多数代码更丑陋，因为在数据库中它们不断地从磁盘加载/卸载数据块并在内存中管理，这显着使代码变得难看。但是，如果你熟悉二叉搜索树，那么我认为你已经足够理解这个概念了。

- goat

Answer 2

好的，这取决于数据存储方式和你想要做什么。

• 如前所述，维护条目的常见结构是B+树。该树被优化用于磁盘，因为实际数据仅存储在叶子节点中 - 键存储在内部节点中。它通常允许非常少量的磁盘访问，因为树的顶部k级可以存储在RAM中，只有少数底层级别将存储在磁盘上，并且每个级别需要进行磁盘读取。
• 其他选择是哈希表。您在内存（RAM）中维护一个“指针”数组 - 这些指针指示包含具有相应哈希值的所有条目的桶的磁盘地址。使用此方法，您仅需要O（1）磁盘访问（通常是处理数据库时的瓶颈），因此速度应该相对较快。
  但是，哈希表不允许有效的范围查询（可以在B +树中高效完成）。

以上所有方法的缺点在于它们需要一个单一键值 - 即如果哈希表或B+树是按照关系的“id”字段构建的，那么如果您按照“键”进行搜索，则变得无用。 如果要保证在关系的所有字段上进行快速搜索，则需要多个结构，每个结构都按不同的键进行 - 这不是很内存有效。 现在，根据具体用途可以考虑许多优化。例如，如果预计搜索次数非常少（比如总操作的loglogN更小），则维护B+树总体效率低于仅将元素存储为列表，并在偶尔进行搜索时 - 只需进行线性搜索。

- amit

---

缺点是，当我在搜索栏中输入两个标签时，像stackoverflow这样的大型数据集如何进行多键搜索？我非常好奇。 - matec

"缺点是..." 我非常好奇，对于像stackoverflow这样的大型数据集，用于多键搜索使用了什么，比如我在搜索字段中写入两个标签？ - matec

Answer 3

非常好的问题，但它可能有许多答案，取决于您的表结构和规范化程度...

通常，在SELECT查询中执行搜索时，DBMS会对表进行排序（它使用归并排序算法，因为该算法适用于I/O磁盘，而不是快速排序），然后根据索引（如果该表有）只需匹配数字，但如果结构更复杂，则DBMS可以在树中执行搜索，但这太深了，请允许我再次查阅我记录的笔记。

我建议激活查询执行计划，这里是Sql Server 2008的示例如何执行此操作。然后使用WHERE子句执行SELECT语句，您将能够开始了解DBMS内部正在发生的情况。

- edgarmtze