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

Question

如果我们给出一个查询:

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

我想知道该搜索将使用哪种算法？

Answer 1

假设您已经为 id 字段建立了索引并且它是唯一的。
该算法是一个 binary search (有优化和改进，但下面是其背后的一般理论)。

假设您有以下有序的数字列表:
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。找到了!

那是 4 次操作对 10 次操作，因此，当二分搜索数据呈指数增长时，二分搜索复杂度将以与全扫描相同的速度增长