mysql使用哪种算法来搜索表中的一行？

Question

如果我们提出查询:

select name from employee where id=23102 and sir_name="raj";

我想知道使用哪种算法进行搜索？

Answer 1

假设您已将id字段编入索引并且它是唯一的.
该算法是二进制搜索(有优化和改进,但下面是它背后的一般理论).

假设您有以下有序的数字列表:
1,45,87,111,405,568,620,945,1100,5000,5102,5238,5349,5520

假设你要搜索5000号,有两种方法.

1. 扫描整个列表,在这种情况下,您将需要检查10个数字(从开始计数到达到5000).
2. 二进制 - >这里是步骤:2a.转到中间数字(620),因为5000大于那个 - >
   2b.您在数字945-5520上执行相同操作,中位数为5102因为5000小于那么 - >
   2c.去945-5102部分的中位数,这是1100,因为它低于5000去1100-5102
   2d 之间的部分.找到了!

这是针对10的4次操作,因此,当二进制搜索数据以指数方式增长时,二进制搜索复杂度将以与完全扫描相同的速率增长