B+Tree索引的演变

1

9

3

页10

2

页号

B+树索引的使用

记录头信息属性之一记录类型，0为普通记录，1为目录项记录，2为最小记录，3为最大记录

·

索引

4

--图7--

28

B+树索引总结

--图2--

记录头信息属性之一记录偏移量（下一条地址相对于本条记录的地址偏移量）

a

建立目录项页记录页

o

注：下一个数据页中用户记录的主键值必须大于上一个数据页中用户记录的主键值，所以 新插入的第4条记录和第3条记录调换位置，新纪录换到了页10（如下图）数据页的编号不是连续的

简化后为

page_no:

0

再分裂一个页出来

d

y

55

234

--图3--

记录放入页中

u

key:

根据我的上一个文件《Mysql之InnoDB数据页（索引页）结构解析》可知，数据表中的记录都是放在页中，InnoDB查找记录时根据搜索条件的不同分为两种情况：1. 以主键为搜索条件时，在页目录中通过二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可找到。2. 非主键列为搜索条件，在数据页中没有对非主键列建立所谓的页目录，就无法使用二分法，这时只能从最小记录开始依次遍历所有记录形成的一个很大的单链表的每条记录，直到找到对应记录为止。不论是上边哪种情况，在没有索引的情况下，我们的前提都是要先定位到数据页才可以，否则不管有没有主键都只能从第一个页沿着双向链表一直往下找，遍历所有数据页，在每页中再根据上边两种情况去找数据，很耗时的。为了解决这个问题，就出现了索引。

1. 每个索引都对应一棵B+树，B+树分为好多层，最下边一层是叶子节点，其余的是内节点。所有用户记录都存储在B+树的叶子节点，所有目录项记录都存储在内节点。InnoDB存储引擎会自动为主键（如果没有它会自动帮我们添加）建立聚簇索引，聚簇索引的叶子节点包含完整的用户记录。2. 我们可以为自己感兴趣的列建立二级索引，二级索引的叶子节点包含的用户记录由索引列 + 主键组成，所以如果想通过二级索引来查找完整的用户记录的话，需要通过回表操作，也就是在通过二级索引找到主键值之后再到聚簇索引中查找完整的用户记录。 3. B+树中每层节点都是按照索引列值从小到大的顺序排序而组成了双向链表，而且每个页内的记录（不论是用户记录还是目录项记录）都是按照索引列的值从小到大的顺序而形成了一个单链表。如果是联合索引的话，则页面和记录先按照联合索引前边的列排序，如果该列值相同，再按照联合索引后边的列排序。 4. 通过索引查找记录是从B+树的根节点开始，一层一层向下搜索。由于每个页面都按照索引列的值建立了Page Directory（页目录），所以在这些页面中的查找非常快。

717

m

11

q

c1列的值

建立目录项

8

目录项2

这个数据页存放的是普通的用户记录，record_type=0

555

这个数据页存储的是目录项记录，record_type=1

当使用多个列的大小作为排序规则时，也就是给多个列建立索引，如让B+树按照c2、c3列大小进行排序：     首先把页和记录按照c2的大小进行排序，在出现c2的值相同的情况下按照c3列大小进行排序。    目录项记录由c2、c3、页号组成，叶子节点记录包含c2、c3和主键c1的值。这种以c2、c3列的大小进行排序建立的B+树称为联合索引本质上也是二级索引，这种联合索引和分别给c2和c3建立索引不同，这种只需要建一棵B+树，而分别建是两颗B+树。

--图1--

页28

看不懂下边记录结构和页结构的可以去看我的另外两个文件《Innodb记录结构---Compact行格式》和《Mysql之InnoDB数据页（索引页）结构解析》

--图5--

5

这个数据页存储的是普通的用户记录，record_type=0

23

页55

B+Tree是以主键为搜索条件的，并且叶子节点存储的完整的用户记录。但当使用其他列作为搜索条件时，如使用c2列作为搜索条件，也就是给c2建立索引，这时候形成的B+树有几个不同点：  1. 使用c2列的值的大小进行页和记录的排序，包括：     （1）页內的记录是按照c2列的大小排序排成一个单向链表     （2）存储用户记录的页按照c2的大小排成一个双向链表     （3）存储目录项的记录页分为不同的层次，同一层次的页根据目录项记录页的记录中c2列的大小排成一个双向链表  2. B+Tree叶子节点存储的不是用户完整的记录，只有主键+c2列值  3. 目录项中存储的也不是页号+主键值，而是页号+c2列的值那么在查询时，从目录项记录页到记录用户真实数据的页中时，再到页中记录，没有完整的记录，只有c2列和主键值，这时就需要拿着主键值去聚簇索引中查找完整记录，这相当于使用了两棵B+树，这个过程叫回表。这种利用非主键索引建立的B+树需要进行一次回表操作才能定位到具体的用户记录，这种B+树称为二级索引或辅助索引（Secondary Index）二级索引目录项记录页由三个部分组成：页号、主键、索引列，这样如果索引列相同，插入新数据时去比较主键值

实际用户记录都存储在B+树的叶子节点存储目录项是内节点或非叶子节点最上层是根节点

n

--图4--

t

10

c3列的值

页17

这玩意倒过来不就是一棵树tree

页8

创建和使用B+树索引的过程中需要注意的一些点：1. B+树索引在空间和时间上都有代价，所以没事儿别瞎建索引。2. B+树索引适用于下边这些情况：    全值匹配    匹配左边的列    匹配范围值    精确匹配某一列并范围匹配另外一列    用于排序    用于分组3. 在使用索引时需要注意下边这些事项：    只为用于搜索、排序或分组的列创建索引    为列的基数大的列创建索引    索引列的类型尽量小    可以只对字符串值的前缀建立索引    只有索引列在比较表达式中单独出现才可以适用索引    为了尽可能少的让聚簇索引发生页面分裂和记录移位的情况，建议让主键拥有AUTO_INCREMENT属性。    定位并删除表中的重复和冗余索引    尽量使用覆盖索引进行查询，避免回表带来的性能损耗。

 联合索引 

这个数据页存放的是表示范围更广的目录项记录，record_type=1

17

c2列的值

建立多级目录项记录的页

        二级索引        （辅助索引）

888

目录项1

关于最左原则：比方说联合索引idx_name_a_b_c中列的定义顺序是a、b、c，如果我们的搜索条件中只有a和c，而没有中间的b，比方说这样：SELECT * FROM person_info WHERE a= 'Ashburn' AND c= '15123983239';这样只能用到a列的索引，b和c的索引就用不上了，因为a值相同的记录先按照b的值进行排序，b值相同的记录才按照c值进行排序

单链表

jdf

页11

页47

这个数据页存放的是普通的目录项记录，record_type=1

这种聚簇索引满足两个特性：1. 使用记录的主键值的大小进行页和记录的排序，包括：      （1）页內的记录是按照主键大小排序排成一个单链表      （2）各个存储用户记录的页也是根据页中用户记录的主键大小排序排成一个双向链表      （3）存放目录项记录的页分为不同的层次，同一层次中的目录项记录页也是根据页中目录项记录中的主键大小排成一个双向链表2. B+树的叶子节点都存储了完整的用户记录

next_record

B+Tree（聚簇索引）

record_type

目录项3

--图6--

最大记录，record_type=3

现在如果我们想通过主键值查找一条用户的记录，大致需要3个步骤：1. 确定目录项记录页2. 通过目录项记录页确定用户记录所在的页3. 在真实存储用户记录的页中找到用户的具体记录

99

页的用户记录中最小 的主键值 

dd

普通的用户记录，record_type=0