10

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

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

在具有 SQL 支持的数据库中。

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

  1. 从表 1 中选择数字，其中名称 =“测试”；
  2. 从表 1 中选择 *，其中名称 =“测试”；

1 从 Table1 中搜索名称为 Test 的数字，2 在所有列中搜索名称 Test。

我了解函数的概念，但是我有兴趣了解搜索的方法是什么？

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

4

3 回答 3

9

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

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

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

还有其他类型的索引，但我想你明白了 - 复制数据并以快速搜索的方式排列它。

在大型数据库上，索引的区别在于等待几分之一秒，而可能需要几天才能完成复杂的查询。

btw- B树不是一个简单易懂的数据结构，遍历算法也很复杂。此外，遍历甚至比您会发现的大多数代码都更丑陋，因为在数据库中，它们不断地从磁盘加载/卸载数据块并在内存中对其进行管理，这大大丑化了代码。但是，如果您熟悉二叉搜索树，那么我认为您已经很好地理解了这个概念。

于 2012-11-13T14:54:37.130 回答
6

好吧，这取决于数据的存储方式以及您要做什么。

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

以上所有方法的缺点是它需要一个键——即如果哈希表或B+树是根据关系的“id”字段构建的，然后你根据“键”搜索——它就变得没用了。
如果您想保证快速搜索关系的所有字段 - 您将需要多个结构，每个结构都根据不同的键 - 这不是非常有效的内存。

现在，根据具体使用情况，有很多优化需要考虑。例如，如果预计搜索次数非常少（比如总操作数的 loglogN 较小），那么维护 B+ 树的效率总体上要低，然后仅将元素存储为列表，并且在极少数情况下进行搜索 - 只需执行线性搜索。

于 2012-11-13T16:06:43.010 回答
1

非常好的问题，但它可以有很多答案，具体取决于表的结构以及标准化的方式......

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

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

于 2012-11-13T14:44:58.683 回答