mysql - Btree 在非索引字段上搜索

Question

我一直在阅读@XenphYan 的回答

How does database indexing work?

但是有些事情我无法理解

Due to the fact that a number of records can only be sorted on one field, we can state that searching on a field that isn’t sorted requires a Linear Search which requires N/2 block accesses (on average), where N is the number of blocks that the table spans. If that field is a non-key field (i.e. doesn’t contain unique entries) then the entire table space must be searched at N block accesses.

首先我无法理解上面的部分。

问题 1. 为什么搜索未排序的字段需要线性搜索 N/2 block 访问？

Whereas with a sorted field, a Binary Search may be used, this has log2 N block accesses. Also since the data is sorted given a non-key field, the rest of the table doesn’t need to be searched for duplicate values, once a higher value is found. Thus the performance increase is substantial.

我也无法理解这一部分，在我看来，上述一点具体是在排序字段上可以使用二分搜索。

我的感受... 根据我的理解，二分搜索仅应用于索引字段。 (即提高搜索性能)

POC:

这是我的 table 的样子

create table sqltemp(
  id INT PRIMARY KEY, 
  name CHAR(50),
  counter INT
);

insert into sqltemp(id,name,counter) values(1,'viren',1),(2,'vikas',2),(3,'vikram',3);  

EXPLAIN ANALYZE  select id from sqltemp where counter=2;

Seq Scan on sqltemp  (cost=0.00..14.25 rows=2 width=4)
   Filter: (increment = 2)

至少 EXPLAIN 命令没有指定任何二进制搜索符号(即它执行 Seq Scan)

所以，我的问题 2 是

问题2:我的理解是否正确，数据库中的二分查找仅适用于索引字段。

Answer 1

Question 1. How come searching on a field that isn't sorted would requires a Linear Search N/2 block accesses?

重要的部分是平均。如果您要从 N 个项目中搜索一个，那么 50% 的情况下，它恰好位于您检查的项目的前半部分中。这只是一种奇特的说法，没有比检查每一行更快的找到目标的方法了。

Question 2: Is my understand correct that Binary Search in DB are only applicable for indexed field.

顺序扫描意味着数据库引擎正在查看每一行，时间复杂度为 O(n)。如果您编写一个利用索引的查询，那么 EXPLAIN 会告诉您它可以使用索引扫描，即 O(log2(n))，即 在大 table 上速度要快得多。要在示例数据库中查看此内容，请尝试:

EXPLAIN ANALYZE  select * from sqltemp where id=2;

主键是一个索引字段，这意味着数据库引擎将其存储在二叉树中。