Mysql-索引-数据结构

Mysql索引-B树/B+树

tip 索引好处初体验：

select count(*) from ydl_user;  -- 5.429
select * from ydl_user where user_id = 1000000; -- 0.355s
select * from ydl_user where user_name = 'Jennifer Susan Johnson';   -- 4.715s

一方面mysql的数据是存储在磁盘上的，另一方面还要满足对日常操作如【增删改查】的高效稳定的支持，我们当然可以采用更好的硬件来提升性能，但是选用合适的数据结构也很关键，innodb采用的是一种名为【b+树】的数据结构。

我们之前已经学习过innodb中的数据是以【行】为单位，存在一个个大小为16k的【页】中，刚才的b+树的作用就是按照一个的组织形式，将所有的【页】组织关联起来。

1、B-树

我们要了解【B+树】，首先要了解一下【B-树】，这里的 B 表示 balance( 平衡的意思)，B-树是一种【多路自平衡的搜索树】，它类似普通的平衡二叉树，不同的一点是B-树允许每个节点有更多的子节点。下图是 B-树的简化图.

在这里插入图片描述

B-树有如下特点:

所有键值分布在整颗树中；
任何一个关键字出现且只出现在一个结点中；
搜索有可能在非叶子结点结束；
在关键字全集内做一次查找，性能逼近二分查找；

2、B+树

【B+树】是【B-树】的变体，也是一种多路搜索树。

【B+树】是【B-树】的不同之处在于:

所有关键字存储在叶子节点
为所有叶子结点增加了一个双向指针

简化 B+树如下图：

在这里插入图片描述

3、选型缘由

问题一：为什么在b-树或b+树中选择？

mysql数据模型更适合用这类数据结构，一条数据中通常包含【id】+【其他列数据】，我们可以很轻松的根据id组织一颗B+树。
我们知道innodb使用【页】（这是inndb管理数据的最小单位）保存数据，一页（16k），b+树中的每个节点都是一页数据。

问题二：为什么选择B+树？

相同的空间，不存放【整行数据】就能存【更多的id】，b+树能使每个节点能检索的【范围更大、更精确，极大的减少了I/O操作，保证b+树的层高较低，通常3到4层的层高就能支持百万级别的访问】。
Mysql是一种关系型数据库，【区间访问】是很常见的一种情况，B+树叶节点增加的双向指针，加强了区间访问性，可使用在范围区间查询的情况。

4、发现索引

我们发现当使用id去查询数据时，效率很高，因为使用id可以利用B+树的特性，加速查询，请看以下两条sql的执行效率：

select * from ydl_user where id = 1                              -- 使用时间0.011s
select * from ydl_user where email = 'm.szi@xwsrnhp.pl'          -- 使用时间4.284s