我已经阅读了 MySQL 松散索引扫描,它作为优化是有意义的,但是,当使用示例 B+树时,我不明白如何有效地跳过节点,因为潜在的匹配会导致执行许多遍历。
拿这个 B+-树:
+-------------+
|A |
+-----------------------------------------+ (5,2) (7,0) +----------------------------------------+
| | | |
| +------+------+ |
| | |
| | |
+------v------+ +------v------+ +------v------+
|B +---------------------------------->C +--------------------------------->D |
+--------+ (2,0) (2,2) +----------+ +---------+ (5,2) (5,4) +---------+ +--------+ (7,0) (8,1) +---------+
| | | | | | | | | | | |
| +------+------+ | | +------+------+ | | +------+------+ |
| | | | | | | | |
| | | | | | | | |
+------v------+ +------v------+ +-------v-----+ +-----v-------+ +------v------+ +-------v-----+ +------v------+ +------v------+ +-------v-----+
|E | |F | |G | |H | |I | |L | |M | |N | |O |
| (0,0) (1,0) +-> (2,0) (2,1) +--> (2,2) (3,0) +-> (4,0) (5,1) +-> (5,2) (5,3) +-> (5,4) (5,5) +-> (6,0) (6,1) +-> (7,0) (8,0) +-> (8,1) (8,2) |
| | | | | | | | | | | | | | | | | |
+-------------+ +-------------+ +-------------+ +-------------+ +-------------+ +-------------+ +-------------+ +-------------+ +-------------+
和查询SELECT (c1), MIN(c2) ... GROUP BY c1
。
现在,根据我的理解,当确定子树不包含不会影响(当前)聚合结果的值时,松散索引扫描将跳过节点。
有了上面的树,我认为遍历将是:
- 一个
- 乙
- 乙
- 找到 (0,0) (1,0)
- 回溯
- 找到 (2,0)
- 跳过 F
- G
- 找到 (3,0)
- 回溯
- H
- 找到 (4,0) (5,1)
- 回溯
- 跳过我
- 大号
- 回溯
- D
- 米
- 找到 (6,0)
- 回溯
- 找到 (7,0)
- ñ
- 找到 (8,0)
- ○
假设回溯没有成本,在这个示例中执行紧密索引扫描(即直接导航所有叶子)的成本不是更低吗?
上面的遍历逻辑有没有错误?或者这是一个过于悲观(因此,不具代表性)的例子?
2 个回答