MySQL源码:Range访问方式相关的数据结构–续

前文着重介绍了MySQL的WHERE条件如何针对单个索引构造对应的SEL_ARG结构,本文是一个补充,将简单介绍多个索引对应的SEL_TREE结构。

对于一个完整的WHERE条件,MySQL会遍历所有可以使用的索引,逐一构造其对应的SEL_ARG结构,所有的SEL_ARG结构以指针数组的形式存放在SEL_TREE->keys中。如果对应索引无法构造SEL_ARG,那么对应的指针为空。

class SEL_TREE :public Sql_alloc { ... SEL_ARG *keys[MAX_KEY]; ... };

gdb打印对应的结构:

(gdb) p $1 $2 = (SEL_TREE *) 0x7f59c4038348 (gdb) p *$1 $3 = { ... keys = {0x0, 0x7f59c4038598, 0x0 }, ... }

SEL_TREE是一个数组,但如果像他的名字,他如果真是一棵树的话,那么将是如下结构:

[ key1 part1 ] [ key1 part2 ] [ key1 part3 ] -\ /- $ $ - / SEL_ARG(-∞, 1) $ ===> SEL_ARG [5,5] ===> $ SEL_ARG [10,10] |...... | |^ $ $ |^ | | next|| $ $ next|| ......| | ||prev $ $ ||prev 0x0 | /--------->| || $ $ v \ | | | || $ $ SEL_ARG [12,12] \------| | | || $ $ [key4]| | | v| $ $ | | | SEL_ARG [2, 2] $=== next_key_part =====| $ | [link of SEL_ARG] | |^ $ | $ | / | next|| $ | $ |--------/ | ||prev $ |===>$ SEL_ARG[11,11] | [key3] | v| $ | $ |^ | \ SEL_ARG [3, 3] $=== next_key_part =====| $ next|| | $ $ ||prev | $ $ v| | SEL_ARG[14,14] [SEL_ARG] | ************************* \ | * structure of SEL_TREE * \------| ************************* [key2]| | | [ key1 part1 ] | / SEL_ARG (-∞,2] $ SEL_ARG [3,5) | | |^ $ /\ Black | | next|| $ / \ | [link of SEL_ARG] | ||prev $ / \ | / | | v| $ SEL_ARG (-∞,2] SEL_ARG (10,∞) |--------/ | | SEL_ARG [3,5) $ Red Red | [key1] |-------->| |^ $ | | next|| $ | | ||prev $ SEL_TREE | v| $ \ SEL_ARG (10,∞) $ $

大图

That’s all. 本文较为简单。

In:

One response to “MySQL源码:Range访问方式相关的数据结构–续”

  1. […] index merge的数据结构和成本评估 2013-03-8  |  14:39分类:MySQL,技术细节  |  标签:index、MySQL、optimizer、Source Code  |  22 views 前面以案例的形式介绍了什么是index merge,以及它的使用场景。本文将介绍index merge实现的主要数据结构以及MySQL如何评估index merge的成本。在开始本文之前,需要先理解Range访问相关的数据结构介绍:SEL_ARG结构,SEL_TREE结构。 目录1. 概述:index merge的数据结构2. 案例1:简单的index merge3. 案例2:单个查询多个index merge4. 成本计算4.1 什么是Rowid-Ordered Retrieval4.2 成本概述4.3 SEL_TREE子树的成本4.4 non-ROR场景的成本计算4.4.1 去重复成本计算概述4.4.2 二级ROWID过滤成本4.4.3 排序比较成本4.4.4 外排序时候的磁盘IO成本4.4.5 合并成本4.4.6 最后的读取4.4.7 根据ROWID取出记录的成本4.5 ROR场景的成本计算4.5.1 索引读取成本4.5.2 合并排序4.5.3 根据ROWID取出记录的成本5 最后 […]

Leave a Reply

Your email address will not be published. Required fields are marked *