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

Question

大家好,我正在研究搜索算法优化.

截至目前,我正在研究数据库.

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

我可以为特定的表编写查询.

1从Table1中搜索名称为Test的数字,2搜索所有列名称Test.

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

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

Answer 1

如果没有索引,那么是,执行线性搜索.

但是,当您将列指定为键时,数据库通常使用B树索引.这些是特殊调整的特殊数据结构格式(高B树分支因子),以便在磁盘硬件上运行良好,其中最重要的耗时因素是搜索操作(磁头必须移动到文件的差异部分) ).

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

还有其他类型的索引,但我认为你明白这一点 - 重复数据并以一种快速搜索的方式排列.

在大型数据库上,索引会在等待一小部分时间与完成复杂查询的可能天数之间产生差异.

btw-B树不是简单易懂的数据结构,遍历算法也很复杂.此外,遍历甚至比您将找到的大多数代码更加丑陋,因为在数据库中,它们不断地从磁盘加载/卸载数据块并在内存中进行管理,这显着地增加了代码.但是,如果您熟悉二叉搜索树,那么我认为您已经足够了解这个概念.

Answer 2

嗯,这取决于数据的存储方式以及您要做的事情.

如已经指出的,用于维护条目的公共结构是B +树.树已针对磁盘进行了优化,因为实际数据仅存储在树叶中 - 并且密钥存储在内部节点中.它通常允许非常少量的磁盘访问,因为k树的顶层可以存储在RAM中,并且只有少数底层将存储在磁盘上并且需要为每个磁盘读取磁盘.
其他替代方案是哈希表.您在内存(RAM)中维护一个"指针"数组 - 这些指针指示磁盘地址,其中包含一个包含所有具有相应散列值的条目的存储桶.使用此方法,您只需要O(1)磁盘访问(这通常是处理数据库时的瓶颈),因此它应该相对较快.
但是,哈希表不允许有效的范围查询(可以在B +树中有效地完成).

以上所有的缺点是它需要一个密钥 - 即如果根据关系的字段"id"构建哈希表或B +树,然后根据"密钥"进行搜索 - 它变得无用.
如果你想保证快速搜索关系的所有字段 - 你将需要几个结构,每个结构根据不同的密钥 - 这不是非常有效的内存.

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

Answer 3

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

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

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