gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-11-29 20:53:02 24 4
gpt4 key购买 nike

我一直在阅读@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:我的理解是否正确,数据库中的二分查找仅适用于索引字段。

最佳答案

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;

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

关于mysql - Btree 在非索引字段上搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37866447/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com