关于Mysql索引的数据结构

2017-04-22 10:09

短信预约 信息系统项目管理师 报名、考试、查分时间动态提醒

关于Mysql索引的数据结构

索引的数据结构

1、为什么使用索引

概念: 索引是存储索引用于快速找到数据记录的一种数据结构，就好比一本书的目录部分，通过目录中对应的文章的页码，便可以快速定位到需要的文章，Mysql 中也是一样的道理，进行数据查找时首先查看查询条件是否命中某条索引，符合则通过索引查找相关数据，如果不符合则需要全表扫描，即需要一条条查找后记录，直到找到与条件符合的记录。

如果当数据没有任何索引的情况下，数据会分布在磁盘上不同的位置上面，当读取数据时，磁盘摆臂需要前后摆动查找数据，这样的操作非常消耗时间。如果数据顺序摆放,那么也需要数次IO操作，依旧非常耗时，如果不借助任何索引结构帮助我们快速定位数据，那么当我们查询时需要逐行扫描、比较。当有上千万数据时，就意味着需要做更多的磁盘IO才能找到对应的数据。

当我们需要查找一条数据时（如：Col2=89）：
CPU需要先去磁盘查找这条记录，找到之后加载到内存，在对数据进行处理。这个过程最消耗时间的就是磁盘I/O（涉及到磁盘的旋转时间[速度较快]、磁头的寻道时间【速度慢、费时】）

假如给数据使用二叉树（又叫搜索二叉树、二叉搜索树）这样的数据结构进行存储，如图：

对col2 添加了索引，就相当于在硬盘上为col2维护了一个索引的数据结构，即二叉树，二叉搜索树的每个节点存储的是k，v结构，key是col2，value是key所在的文件指针，那么对col2添加了索引，这时再去查找col2=89这条记录时，先查询二叉搜索树（二叉遍历查询）。读34到内存中，进行对比 89 > 34,继续右侧查询读89到内存。比对之后返回指针数据。在根据当前的value快速定位到对应的数据地址，此时我们发现，只需要两次I/O就可以定位到记录，查询的速度就提高了。

这就是我们为什么要建索引，建索引的目的就是为了减少磁盘I/O，加快查询效率。

2、索引及其优缺点

2.1索引概述

Mysql官方对索引的定义为：索引（index）是帮助mysql高效获取数据的数据结构。

索引的本质 是数据结构，可以简单的理解为‘排好序的快速查找数据结构’，满足特定的查找算法。这些数据结构以某种方式指向数据，这样就可以在这些数据结构的基础上实现高级查询算法。

索引是在存储引擎中实现的,因此每种存储引擎的索引不一定完全相同，并且每种存储引擎不一定支持所有的索引类型。同时存储引擎可以定义每个表的最大索引和最大索引长度,所有的存储引擎支持每个表至少16个索引，总索引长度最大为256字节。有些引擎支持更多的索引数和更大的长度。

2.2优点

降低数据库的IO成本，这也是建立索引最主要的原因。
可以创建唯一索引，保证数据库中表数据的唯一性。
在实现数据的参考完整性方面，可以加速表与表之间的连接。换句话说，对于子表和父表联合查询时可以提高查询速度。
在使用分组和排序子句进行查询时，可以显著的减少查询中分组和排序的时间,减少CPU消耗

2.3缺点

创建索引也有许多不利的方面，主要表现在以下几点

创建和维护索引需要耗费时间,随着数据的增加，耗费的时间也随之增加。
创建索引需要占用磁盘空间, 除了数据表占据数据空间之外，每个索引还要占用一定的物理空间，存储在磁盘上如果有大量的索引，索引文件就可能比数据文件更快达到最大文件尺寸。
虽然索引大大提高了查询速度，同时却也会降低更新表的速度，当对表中的数据进行增加、删除、修改的操作，索引也要动态维护，这样就降低了数据的维护速度。

因此，在选择使用索引时，需要综合考虑使用索引的优缺点。

提示：索引可以提高查询速度，但是会影响插入记录的速度，在这种情况下，最好的办法是删除表中索引，然后插入数据，完成后在创建索引。（在频繁的更新索引时，重新建立索引反而会消耗比较少的时间）

3、InnoDB索引的推演

3.1 索引之前的查找

一个简单的查询：

select 列名列表 from table where 列名 = xxx

在一个页中查找：

假设目前表中的记录比较少，所有的记录都可以被放在一个页中，在查找记录的时候可以根据搜索条件的不同分为两种情况
- 以主键为搜索条件：
  
  在页目录中使用二分法快速定位到对应的槽，然后便利该槽对应分组中的记录即可快速找到制定记录
- 以其他列作为搜索条件
  
  因为在数据页中并没有对非主键列建立所谓的页目录，所以无法通过二分法查找，这种情况只能从最小记录开始依次遍历单链表中的每条记录，然后对比每条记录是不是符合搜索条件，显然，这种查找的方式效率是非常低的。
在很多页中查找：

大部分情况下我们表中存放的记录都是非常多的，需要很多的数据页来存储这些记录。在很多页中查找记录的话可以分为两个步骤：
- 定位到记录所在的页。
- 从所在的页内中查找相应的记录。
在没有索引的情况下，不论是根据主键列或者其他列的值进行查找，由于我们并不能快速的定位到记录所在的页，所以只能从第一个页沿着双向链表一直往下找，在每一个页根据上面的查找方式去查找指定的记录。因为要遍历所有的数据页，所以这种方式显然是超级耗时的，如果表有一亿条数据呢，索引应运而生。

数据存储的基本单位称之为数据页。

一个数据页的大小为16kb。

3.2 设计索引

首先建立一个表：

CREATE TABLE index_demo(
	c1 int,
	c2 int,
	c3 char,
	PRIMARY KEY(c1)
) ROW_FORMAT = Compact;

index_demo表有两个int类型的列，1个char类型，规定了c1主键，使用Compact行格式来实际存储记录。这里简化了index_demo的行格式示意图：

其中：

record_type:记录头信息的一项属性，表示记录的类型，0表示普通记录，2表示最小记录。3表示最大记录、1暂时没用过，下面讲。
next_record:记录头信息的一项属性,表示下一条记录的地址偏移量，用箭头表示下一条记录是谁。
各个列的值: 这个只记录的三个列，分别是c1、c2、c3.
其他信息:除了上述三种信息以外的所有信息，包括其他隐藏列的值以及记录的额外信息。

把一些记录放到数据页的示意图就是：

1、`一个简单的设计方案`

我们在根据某个搜索条件查找一些记录，为什么要便利所有的数据页呢？因为在各个页中的记录并没有规律，我们并不知道我们的搜索条件匹配那些页中的记录，所以不得不依次便利所有的数据页。所以如果我们想要快速定位到需要的记录在那些数据页中该怎么办。我们可以为快速定位记录所在的数据页而建立一个目录，那建立目录时必须完成下边这些事:

下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值：

假设：每个数据页只能存放三个记录(实际非常大，可以存很多)，那么这些记录已经按照主键值的大小串联成一个单向链表了。如图：

当我们再次插入一条记录时，因为页10 最多放3条记录，所以不得不再次分配一个新页：

新分配的数据页编号可能并不是连续的，他们只是通过维护这上一个页和下一个页的编号而建立了链表关系，另外页10中用户记录最大的主键值是5，而页28中有个记录主键值是4，所以在插入主键值为4的记录时需要伴随着一次记录移动，也就是需要把4和5 进行调换。

这个过程表名了在对页中的记录进行增删改查时，必须通过一些诸如此类的记录移动的操作来保持这个状态的成立：下一个数据页中的用户记录的主键值必须大于上一个页中用户记录的主键值，这个过程称之为页分裂。

由于数据页的顺序可能是不连续的，所以在向index_demo 中插入数据后，可能是这样的结果：

因为这些16kb的页在物理存储上是不连续的，所以想要从这些页中根据主键值快速定位记录所在页，需要给他们做个目录。每个页对应一个目录项，每个目录项包括下边两个部分

1. 页的用户记录中最小的记录值用key表示
2. 页号： 用page_no表示（数据页地址）

所以上面几个数据页做好的目录就是这样：

以页28为例，对应目录项2，这个目录的包含着页号28(也就是页指针)以及最小主键值5，我们只需要把这个目录项在物理存储器上连续存储（比如：数组），可以实现根据主键值快速查找某条记录的功能了。

比如：查找主键为c1为20的记录，具体分两步

1. 先从目录项根据`二分法`确定出主键值为20的记录在`目录项三`中，对应的页是页9
1. 在根据前边说的在页中查找记录的方式去页9中定位具体的记录。

那上面这些个过程就是针对主键为c1的列建立了一个目录项的方案，这个方案就叫做索引

2、InnoDB的索引方案

迭代一次：目录项记录的页
迭代两次：多个目录项记录的页
迭代三次：目录项记录页的目录页
B+Tree

在第0层（最底层）中存放这具体数据，数据与数据之间为单向链表，页与页之间为双向链表。

B+Tree树：不论是存放用户记录的数据，还是存放目录项记录的数据页，我们都把他们放在b+树这个数据结构中，所以我们也这些数据页为节点，我们的实际用户记录其实都存放在b+树最底层的节点上，这些节点也称之为叶子节点，其余用来存放目录项的节点称之为非叶子节点或者内节点，其中B+树最上面的节点称为跟节点。

B+Tree树节点可以分为很多层，规定最下面的那层，也就是存放记录的第0层，之后依次往上加。

假设：所有存放记录的叶子节点能存放100条用户记录，所有存放目录项记录的内节点存放100条目录项，那么：

通常在一般情况下，我们用到的B+树不会超过4层. 节点层越高I/O 次数越多

3.3 常见索引概念

索引按照物理实现的方式，索引可以分为2种聚簇(聚集)索引和非聚簇(非聚集)索引，我们也把非聚集索引称为二级索引或者辅助索引。

3.3.1 `聚簇索引`

聚簇索引并不是一种单独的索引类型，而是一种数据存储方式（所有的用户记录都存储在了叶子节点），也就是所谓的索引即数据，数据即索引

术语聚簇表示数据行与相邻的键值聚簇的存储在一起

特点：

使用记录主键值的大小进行记录和页的排序包括三个方面的含义

页内的记录是按照主键的大小顺序排成一个单向链表。
各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表。
存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。

B+树的叶子节点存储的是完整的用户记录。

所谓完整的用户记录，就是指这个记录中存储了所有列的值（包括隐藏列）。

我们把具有这两种特性的B+树称为聚簇索引，所有完整的用户记录都存放在这个叶子节点处，这种聚簇索引应不需要们在mysql语句中显式的使用index语句去创建，innodb存储索引会自动的为我们创建局促索引。

优点：

数据访问更快，因为聚簇索引将索引和数据保存在同一个B+树中，因此从聚簇索引中获取数据比非聚簇索引更快。
聚簇索引对于主键的排序查找和范围查找速度非常快。
按照聚簇索引排列顺序，查询显示一定范围数据的时候，由于数据都是紧密相连，数据库不用从多个数据块中提取数据，所以节省了大量的io操作

缺点：

插入速度严重依赖于插入顺序，按照主键的顺序插入是最快的方式，否则出现页分裂，严重影响性能，因此，对于innodb表，我们一般会定义一个字增的id列为主键。
更新主键的代价很高，因为会导致被更新的行移动，因此对于innodb表我们一般定义主键为不可更新。
二级索引访问需要两次索引查找，第一次找到主键值，第二次根据主键找到行数据。

限制：

对于Mysql 数据库目前只有innodb数据引擎支持聚簇索引，而myisam并不支持聚簇索引。
由于数据物理存储排序方式只有一种，所以每个Mysql的表只能有一个聚簇索引。一般情况下就是该表的主键
如果没有定义主键，innodb就是选择非空的唯一索引代替，如果没有这样的索引，innodb会隐式的定义一个主键来作为聚簇索引。
为了充分利用聚簇索引的聚簇特性，所以inndodb表的主键列尽量选用有序的顺序id，而不建议用无序的id，比如uid、md5、hash等作为主键，无法保证数据的顺序增长。

3.3.2 `二级索引`

上面介绍的聚簇索引只能是在搜索条件上是主键值时才能发挥作用，因为B+树中的数据都是按照主键进行排序的，那如果我们以别的列来作为搜索条件该怎么办。肯定不能从头到尾沿着链表一次遍历记录。

可以多建几颗b+树，不同的b+树采用不同的排序规则，比如说c2列的大小作为数据页、页中记录的排序规则在建立一颗B+树。效果如图：

这个B+树与上面的介绍的聚簇索引有几处不同：

使用记录c2列的大小进行记录和页的排序，这包括三个方面的含义：
- 页内记录是按照c2的大小顺序进行一个单向链表。
- 各个存放用户记录的页也是根据页中记录的c2列大小顺序排成一个双向链表。
- 存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的c2列顺序排成一个双向链表。
B+树的叶子节点存储的并不是完整的用户记录，而是c2列(当前二级索引列)+主键这两个列的值。
目录项记录页中不在是主键+页号的搭配，而是c2列+页号的搭配。

所以如果我们想通过c2列的值查找某些记录的话就可以使用刚才建立的B+树，查询c2=4的记录，过程如下：

确定目录项页

从根页44 快速定位目录记录所在的页42上面（二级索引列c2。2<4<9 ）
通过目录项记录页确定用户记录真实的页

在页42中，可以快速定位到实际存储用户记录的页，但是由于c2列并没有唯一约束，所以c2值可能分布在多个数据页，所以可以确定在页34和页35中
在真实存储用户记录的页中定位到具体的记录

在页34和35中定位到具体的c2列和主键的记录。
但是这个B+树中叶子节点只存储了c2（二级索引）和c1（主键）两个列，所以我们必须在根据主键值去聚簇索引中再次查询一次完整的用户记录。

概念：回表

我们根据这个以c2列大小排序的B+树只能确定我们要查找记录的主键值，所以如果我们根据c2列查询完整的记录的话，仍然需要在聚簇索引中在查一遍，这个过程称之为回表,也就是根据c2列的值查询一条完整的用户记录需要用到两颗B+树。

小结：聚簇索引和非聚簇索引的原理不同，在使用上也有一些区别

聚簇索引的叶子节点存储的就是我们的数据记录，非聚簇索引的叶子节点存储的是数据位置。非聚簇索引会影响数据表的物理存储顺序。
一个表只能有一个聚簇索引，因为只能有一个排序存储的方式，但是可以有多个非聚簇索引，也就是多个索引目录提供数据检索。
使用聚簇索引的时候，数据查询效率高,但是如果对数据进行插入、删除更新等操作，效率会比非聚簇索引低。

3.3.3 `联合索引`

我们页可以同时以多个列的大小作为排序规则，也就是同时为多个列建立索引，比方说我们想让B+树按照c2和c3列的大小进行排序，这个包含两层含义：

先把各个记录和页按照c2排序
在记录的c2列相同的情况下，采用c3列进行排序

为c2和c3列建立的索引示意图如下：

如图所示：

每条目录项记录都由c2、c3、页号三个部分组成，各条记录先按照c2列的值进行排序，如果记录的c2列相同则按照c3值排序
B+树叶子节点处的用户记录由c2、c3和主键c1列组成。

注意一点，以c2、c3的大小为排序规则建立的b+树称为联合索引，本质也是一个二级索引，与普通的二级索引不同的是：

建立联合索引只会建立如上图一样的一颗B+树。
为c2和c3分别建立索引会分别以c2和c3的大小排序规则建立两颗b+树

3.4 InnoDB引擎的B+树索引的注意事项

3.4.1 根页面位置万年不动

实际上B+树的形成过程是这样的：

每当为某个表创建一个B+数索引的时候，都会为这个索引创建一个根节点页面，最开始没有数据的时候，B+树索引对应的根节点中既没有用户记录，也没有目录项记录
随后向表中插入用户记录时，先把用户记录存储到这个根节点中。
当根节点中的可用空间用完继续插入记录，此时会将根节点中的所有记录复制到一个新分配的页，比如页a中。然后对这个新页进行页分裂操作，得到另一个新页，比如页b。这时新插入的记录根据键值(也就是聚簇索引中的主键值，二级索引中对应索引列的值)的大小就会被分配到页a或者页b中，而根节点便升级为目录项记录的页。

特别注意的是：一个B+数自诞生起，便不会在移动，这样只要我们对表进行建立索引，那么他的根节点的页号便会被记录到某个地方，然后凡是InnoDB存储引擎需要用的索引的时候，都会从那个固定的地方取出根节点的页号。从而访问这个索引。

3.4.2 内节点中目录项唯一性

为了让新加入的记录找到自己在哪个数据页里，我们必须要保证在B+树里的同一层内的目录项记录除了页号这个字段以外是唯一的，所以对于二级索引的内节点的目录项记录的内容实际上是由三个部分构成的。

索引列的值
主键值
页号

也就是我们把主键值页添加到二级索引内节点中的目录项记录了，这样就能保证B+树每一层节点中各条目录项记录除页号这个字段以外是唯一的。所以最后肯定能定位唯一的一条目录项记录。

3.4.3一个页面最少两条记录

一个B+树只需要很少的层级就可以轻松存储数亿条记录，查询速度相当不错！这是因为B+树本质就是一个大的多层目录，每经过一个目录时就会过滤掉很多无效子目录，知道最后访问到存储真实数据的目录。

那如果一个大的目录中只存放一个子目录是什么效果呢？那就是目录层级非常多，而且最后那个存放真实数据的目录中只能存放一条记录，查询时间很长只为了一条记录，所以InnoDB的一个数据页至少存放两条记录。

4、MyISAM中的索引方案

`B树索引适用存储引擎如表所示：`

索引	MyISAM	InnoDB	Memory
B-Tree	支持	支持	支持

即使多个存储引擎支持同一种索引，但是他们实现的原理是不同的。InnoDB和MyISAM默认的索引是Btree索引，而Memory默认索引是HASH索引。

MyISAM引擎使用B+tree作为索引结构，叶子节点的data域存放的是数据记录的地址

4.1 MyISAM索引的原理

我们都知道InnoDB引擎中索引即数据，也就是聚簇索引的那颗B+树叶子节点中已经把所有完整的用户记录都包含了，而MyISAM的索引方案虽然页使用树形结构，但是却将索引和数据分开存储:

将表中记录按照记录的插入顺序单独存储在一个文件中，称之为数据文件。这个文件并不划分为若干个数据页。有多少记录就往这个文件中塞多少记录，由于插入数据的时候并不需要刻意按照主键大小排序，所以我们并不能在这些数据上使用二分法查找。
使用MyISAM存储引擎的表会把索引信息另外存储到一个称为索引文件的另一个文件中。MyISAM会单独为表的主键创建一个索引，只不过在索引的叶子节点中存储的不是完整的用户记录，而是主键值+数据记录地址的组合。

MyISAM的索引文件仅仅保存数据记录的地址，在MyISAM中主键索引和二级索引在结构没任何区别，注视主键索引要求key是唯一，而二级索引的key是可以重复的。

同样是一颗B+树，MyISAM存储引擎中data域保存的并非具体的用户结构，而是数据记录的地址。因此MyISAM中索引检索的算法为：首先按照B+树搜索算法来进行搜索索引，如果指定的key存在，则取出data域的值,然后以data域的值为地址，读取对应地址的数据记录。

4.2 MyISAM和InnoDB对比

MyISAM的索引方式都是"非聚簇"的，与innodb包含一个聚簇索引是不同的.

在InnoDB中，我们只需要根据主键值对聚簇索引进行一次查找就能找到对应的记录，而在MyISAM中却需要一次回表的操作，意味着MyISAM中建立的索引相当于全是二级索引。
InnoBD的数据文件本身就是索引文件,而MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。
InnoDB的非聚簇索引data域存储对应的主键值，而MyISAM存储对应记录的地址。换句话说，InnoDB的所有非聚簇索引都引用主键作为data域。
MyISAM的回表操作是十分快的，因为它拿到的是地址的偏移量去获取数据的，反观InnoDB是通过获取主键之后在去簇聚索引中获取记录，虽然说不页不慢，也比不上直接地址去访问。
InnoDB要求必须有主键（MyISAM可以没有），如果没有显式指定，则Mysql会自动选择一个可以非空且唯一的数据记录的列作为主键，如果没有，则会自动为InnoDB生成一个隐式的字段作为主键，这个长度为6个字节，类型为长整型。

小结：

了解不同的存储引擎的索引实现方式对于正确使用和优化索引都是非常有帮助的。比如：

当我们知道innodb索引的实现后，就很容易明白不建议使用过长字段作为主键，因为所有的二级索引都是引用的主键索引，过长的主键会令二级索引变得过大。
用非单调的字段作为主键在innodb中也不好，因为innodb本身就是一个b+树，非单调主键会造成在插入新纪录时，数据为了维持B+tree的特性而频繁的分裂调整，十分低效。而使用自增字段作为主键式非常好的方式。

5、索引的代价

索引是个好东西，但是不能乱建，他在空间和时间上都会有消耗。

空间上的代价
- 每次建立索引都要为它建一颗B+树，每一颗B+树的每个节点都是数据页，一个页默认会占用16KB的空间，一颗很大的B+树由许多数据页组成，那就是一片很大的存储空间
时间上的代价
- 每次对表的数据进行增删改查，都需要去修改各个B+树索引。而我们说过，B+树每层节点都是按照索引列的顺序排序组成的双向链表。不论是叶子节点的记录，还是内节点的记录都是按照索引列的值从小到大的顺序形成了一个单向链表，而增删改的操作可能会对节点和记录的排序造成破坏，所以存储引擎需要额外的时间进行一些记录移位、页面分裂、页面回收等的操作来维护好节点和记录的排序。如果我们建立了许多索引，每个索引对应B+树都要进行相关的维护，给性能拖后腿.

一个表的索引建立的越多，就占用越多的存储空间。再增删改的时候性能就会越差，为了建立又好又少的索引，我们得学学这些索引是在那些条件下起作用的。

6、MySQL数据结构选择的合理性

从MySQL的角度来讲，不得不考虑的一个现实的问题就是磁盘的IO，如果我们能让索引的数据结构尽量的减少硬盘的IO操作，所消耗的时间也就越少，可以说磁盘的IO操作次数对索引的使用效率至关重要。

查找都是索引操作，一般来说索引非常大，尤其是关系型数据库，当数据量比较大的时候，索引的大小有可能几个G甚至更多，为了减少索引在内存中的占用，数据库索引是存储在外部磁盘的，当我们利用索引是不可能把整个索引全部加载到内存，只能逐一加载，那么Mysql衡量查询效率的标准就是IO次数。

6.1 全表遍历

进行顺序的全表扫描每行数据

6.2 Hash结构

hash本身是一个函数，又被称为散列函数，它可以帮助我们大幅提升检索数据的效率。

Hash算法是通过某种确定性的算法（如：MD5、SHA1、SAH2、SAH3）讲输入转变为输入。相同的输入永远可以得到相同的输出，假设输入内容有微小的偏差，在输出种通常都会有不同的结果。

加速查找速度的数据结构，常见的有两类：

树,例如平衡二叉树，查询插入修改和删除的平均时间复杂度都是o(log2n);
哈希，例如HashMap(无序)，查询插入修改删除的平均时间复杂度是都o(1);

采用Hash进行检索效率非常高，基本上一次检索就可以找到数据，而B+树需要自顶向下一次查找，多次访问节点才能找到数据，中间需要多次IO，从效率来讲Hash比B+树更快。

Hash结构效率高，那么为什么索引结构要设计成树型呢？原因如下：

Hash索引仅能满足（=、<>）和in查询。如果进行范围查询，哈希型索引，时间复杂化会退化为O（n）而树型的有序特性，依然能保持O（log2n）的高效率。
Hash索引还有一个缺陷，数据的存储是没有顺序的，在OrderBy的情况下，使用Hash索引还需要对数据进行重新排序。
对于联合索引的情况，Hash值是将联合索引键合并后一起计算的，无法对单独的一个键或者几个索引键来查询。
对于等值查询来说，通常Hash索引的效率更高，不过也存在一种情况，就是索引列的重复值如果很多，效率就会降低。这是因为遇到Hash冲突时，需要遍历桶中的行指针来比较，找到查询的关键字，非常耗时。所以Hash索引通常不会用到重复值多的列上，比如列为性别、年龄的情况

6.3 二叉搜索树

我们利用二叉树来作为搜索条件，那么磁盘的IO次数和索引树的高度是相关的。

二叉搜索树的特点
- 一个节点只能有两个子节点，也就是一个节点度不能超过2
- 左子节点< 本节点;右子节点>=本节点，比我大的向右，比我小的向左。
查找规则

我们先来看看最基础的二叉搜索树，搜索某个节点和插入节点的规则一样，我们也假设搜索插入的数据为key：
- 如果key大于根节点，则在右子树查找；
- 如果key小于根节点，则在左子树查找；
- 如果key等于根节点，直接返回根节点。

我们对一个数列（34,22,89,5,23,77,91）创造出来的一个二分查找树如下：

二叉树搜索也存在特殊情况，有时候二叉树的搜索深度非常大，比如我们给的数列的顺序是（2,22,23,34,77,89,91）如图：

虽然也属于二分查找树，但是性能上已经退化成一个链表，那么查询的数据的时间复杂度变成了O(n). 为了提高查询效率，就需要减少磁盘的IO数，为了减少磁盘的io，就需要降低树的高度，需要把原来瘦高的树结构变得矮胖，树的每层分叉越多越好。

引入AVL树。

6.4 AVL树

为了解决上面二叉树退化成链表的问题，人们提出了平衡二叉搜索树，又称为AVL树，它在二叉搜索树的基础上增加了约束，具有一下特点：

它是一颗空树或它的左右子树的高度差的绝对值不超过1，并且左右两个子树都是一个平衡二叉树

这里说一下，常见的平衡二叉树有多种，包括平衡二叉搜索树、红黑树、数堆、伸展树。平衡二叉搜索树是最早提出来的自平衡二叉树,当我们提到平衡二叉树时，一般是指的平衡二叉搜索树。事实上第一棵树就属于平衡二叉搜索树，搜索时间复杂度就是O(log2n)。

数据查询的时间主要依赖于磁盘Io的次数，如果我们采用二叉树的形式，即使通过平衡二叉搜索树进行了改进，树的深度也是O(log2n)，当n比较大时深度也是比较高的。如图所示：

每访问一次节点就需要对磁盘进行一次IO，对于上面的树来说，我们需要进行5次IO 虽然平衡二叉树的效率高，但是树的深度也很高，就意味着io的次数多，会影响整体的一个效率。

针对同样的数据，如果我们把二叉树改成M叉树(M>2)呢当m=3时，同样的31个节点可以有下面的三叉树来进行存储：

你能看到此时树的高度降低了，当数据量n大的时候，以及树的分叉树M大的时候，M叉树的高度会远小于二叉树的高度(M>2).所以，我们需要把树从瘦高变成矮胖。

引入B树。

6.5 B-Tree

B树的英文是Balance tree，也就是多路平衡查找树。简写就是B-Tree。他的高度远远小于平衡二叉树的高度。B树的结构如图：

B树作为多路平衡查找树,它的每一个节点最多包括M个子节点，M称为B树的阶。每个磁盘种包括了关键字和子节点的指针 。如果一个磁盘块中包括了x个关键字，那么指针树就是x+1。对于一个100阶的B树来说，如果有三层的话最多可以存储大约100万的索引数据。对于大量的索引数据来说，采用b树的结构是非常适合的，因为树的高度远小于二叉树的高度。

B树在插入和删除节点的适合如果导致树不平衡，就通过自动调整节点的位置来保持树的自平衡。
关键字集合分布在整个树中，即叶子节点和非叶子节点都存放数据。搜索有可能在非叶子节点结束。
其搜索性能等价于在关键字全集内做一次二分查找。

与B+树的区别在于，B+树的所有数据都在叶子节点存储，而B树则叶子节点和非叶子节点都存放数据。

6.6 B+Tree

B+ 树也是一种多路平衡查找树,基于B树做出了改进，主流的DBMS都支持B+树的索引方式，比如Mysql。相比较B-Tree，B+Tree更适合文件索引系统。

B+树和B树的差异在于以下几点：

有k个孩子(叶子节点数据页)的节点就有k个关键字(目录项记录)。也就是孩子数量=关键字，而B树中，孩子数量=关键字+1。
B+树中非叶子节点的关键字也会同时存在子节点中，并且是子节点中所有关键字的最大（或最小）。
非叶子节点仅仅用于索引，不保存数据记录，跟记录有关的信息都存放在叶子节点中。而B树中非叶子节点即保存索引，也保存数据记录。
所有关键字都在叶子节点出现。叶子节点构成一个有序链表，而且叶子节点本身按照关键字从小到大顺序链接。

B+树和B树有个根本性的差异在于,B+树的中间节点并不直接存储数据。这样有什么好处呢？

首先，B+树查询效率更稳定。因为B+树每次只有访问到叶子节点才能找到对应的数据，而在B树种，非叶子节点也会存数据，这样就会造成查询效率不稳定的情况，有时候访问到非叶子节点就能找到数据，而有时候需要访问到叶子节点。

其次。B+树的查询效率更高，这是因为通常B+树比B树更加的矮胖(阶数更大，深度更低)，查询所需要的磁盘IO也会更少，同样的磁盘页大小，B+树可以存储更多的节点关键字。

不仅是对单个关键字的查询上，在查询范围上B+树的效率也比B树高，，这是因为所有关键字都出现在B+树的叶子节点，叶子节点之间会有指针，数据又是递增的，这使得我们范围查找可以通过指针链接查询。而在B树中则需要中序遍历才能完成查询范围的查找，效率要低很多。

B树和B+树都可以作为索引的数据结构，在Mysql 中采用的是B+树。

但是B树和B+树都有自己的应用场景，也不能说B+树就一定比B树好。

思考：为了减少io ，索引树会一次性加载吗？

数据库索引是建立在磁盘上的，如果数据量很大，必然导致索引的大小也会很大，超过几个G。
当我们利用索引查询的时候，是不可能讲全部的几个G的索引都加载进内存的，我们能做的只能是，逐一加载每个磁盘页，因为磁盘页对应着索引树的节点

思考： B+树的存储能力如何？为何说一般查找行记录，最多只需要1~3次磁盘I/O?

InnoDB存储中页的大小为16KB，一般表的主键类型为int(4个字节)或BIGINT(8个字节),指针类型也一般为4或8个字节，也就是一个数据页中大概存储16KB/(8b+8b)= 1k 个键值，因为是一个估值，为了方便计算，这里的K取值为10^3. 也就是说一个深度为3的B+Tree索引可以维护10^3 * 10^3 * 10^3=10亿条记录。在实际情况中 每个节点可能不能填充满，因此在数据库中，B+Tree的高度一般是1~4层。Mysql的InnoDB存储引擎在设计时是讲根节点常驻内存的，也就是在查找时最多再进行1-3次磁盘的IO。

思考:为什么说B+树比B树更适合实际应用中操作系统的文件索引和数据库索引？

B+树的磁盘读写代价更低。
B+树的查询效率更稳定。

思考:Hash索引与B+树索引的区别？

Hash索引不能进行范围性的一个查找，因为hash指向的数据是无序的，而B+树的叶子节点是个有序的链表。
Hash索引不支持联合索引的最左侧原则(即联合索引的部分索引无法使用)，而B+树可以。对于联合索引来说，Hash索引在计算Hash值得时候将索引键合并后再一起计算Hash值，所以不会针对每个索引单独计算hash值。因此如果用到联合索引的一个或者多个索引时，无法被利用。
Hash不支持OrderBy排序，以为Hash索引指向的数据无序，因此无法起到排序的作用。而B+树索引数据是有序的，可以起到对该字段order by排序优化的作用，同理，我们也无法对hash索引进行模糊查找,而B+树使用模糊查询的方式时，like后面后模糊查询的话就可以起到优化作用。
InnoDB不支持Hash索引。