数据库中查询搜索的算法是什么？ [英] What is the algorithm for query search in the database?

问题描述

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

在数据库中有/ SQL支持。

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

1. 从表1中选择Number，其中Name =Test;


2. 从Table1中选择*，其中Name =Test;

1从表1中查找名称为测试的数字，2个搜索所有列的名称为测试。

我理解这个功能的概念，但是我有兴趣学习搜索的方法是什么？

线性搜索，从第一个索引到第n个索引，只要条件为真，就可以获得这个索引，因此具有O（n）速度，还是具有加速其进程的唯一算法？

解决方案

如果没有索引，那么是的，线性搜索是pe

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

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

还有其他类型的索引，但我认为你得到的想法 - 重复的数据，并以快速搜索的方式进行排列。

开一个大的数据库，索引在等待一秒的时间之间有所不同，相对于复杂查询的可能天数完成。

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

Good day everyone, I'm currently doing research on search algorithm optimization.

As of now, I'm researching on the Database.

In a database w/ SQL Support.

I can write the query for a specific table.

1. Select Number from Table1 where Name = "Test";
2. Select * from Table1 where Name = "Test";

1 searches the number from Table1 from where the Name is Test and 2 searches all the column for name Test.

I understand the concept of the function however what I'm interested in learning what is the approach of the search?

Is it just plain linear search where from the first index until the nth index it will grab so long as the condition is true thus having O(n) speed or does it have a unique algorithm that speeds its process?

解决方案

If there's no indexes, then yes, a linear search is performed.

But, databases typically use a B Tree index when you specify a column(s) as a key. These are special data structure formats that are specifically tuned(high B Tree branching factors) to perform well on magnetic disk hardware, where the most significant time consuming factor is the seek operation(the magnetic head has to move to a diff part of the file).

You can think of the index as a sorted/structured copy of the values in a column. It can be determined quickly if the value being searched for is in the index. If it finds it, then it will also find a pointer that points back to the correct location of the corresponding row in the main data file(so it can go and read the other columns in the row). Sometimes a multi-column index contains all the data requested by the query, and then it doesn't need to skip back to the main file, it can just read what it found and then its done.

There's other types of indexes, but I think you get the idea - duplicate data and arrange it in a way that's fast to search.

On a large database, indexes make the difference between waiting a fraction of a second, vs possibly days for a complex query to complete.

btw- B tree's aren't a simple and easy to understand data structure, and the traversal algorithm is also complex. In addition, the traversal is even uglier than most of the code you will find, because in a database they are constantly loading/unloading chunks of data from disk and managing it in memory, and this significantly uglifies the code. But, if you're familiar with binary search trees, then I think you understand the concept well enough.

这篇关于数据库中查询搜索的算法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！