Mysql索引数据结构

下面列举了常见的数据结构

• 二叉树
• 红黑树
• Hash表
• B-Tree（B树）

Select * from t where t.col=5

我们在执行一条查询的Sql语句时候，在数据量比较大又不加索引的情况下，逐行查询并进行比对，每次需要从磁盘上查找，每行数据可能在磁盘不同的位置，数据比较靠后的话，一千万数据可能要比对几百万，很耗费资源。

Mysql衡量查询效率的就是磁盘IO次数，那么Mysql中应该采用什么样的数据结构存储数据呢，以及为什么要使用那个数据结构呢。

二叉树

大多数人都知道，如果加上索引之后。把数据放在二叉树里面，查询会快很多，但是还有一种特殊的情况：

把一个递增列的索引放入二叉树中，列id作为等于5查询目标，就会从col为1开始搜索，这样要搜索几次?二叉树插入的数据如果大于本身，会放在父节点的右下角，小的会放在父节点的左下角，因此形成了这样像链表一样的结构，其实本质还是二叉树。

需要从根节点遍历，经过5次的查找，每个节点都存储在磁盘上，每查一个节点需要跟磁盘做一次IO交互，效率相比之前没加索引也没有太大提升,这显然不是Mysql的索引结构。

红黑树

HasMap的数据结构就是红黑树，原来是数组加链表，现在优化到了数组加红黑树。

红黑树本质还是二叉树，还有一个名字又叫平衡二叉树。当一边子节点比另一边高太多的时候，会自动旋转平衡。当数据量比较大的时候比如1000万，红黑树存储的高度就可能达到几十。如果数据量越大树的高度就会越高。每查一个节点要进行一次磁盘IO交互。树的高的越高查找效率越低，很显然红黑树也不是Mysql的数据结构，早期版本Mysql有用到红黑树，现在版本没有用到红黑树。那么能不能对红黑树做点改造。

B-Tree

树的高的越高查找效率越低，那么将树高缩小，比如限制在5层，把一层存放更多元素。把一个节点的数据在磁盘同一个区域全部查出来放到内存，只做一次IO查找，就可以查到很多索引信息。B树又叫平衡多叉树。

索引值和具体data都在每个节点里，而节点的位置不固定，最好的情况查找值就在第一层。

B树的特点就是每层节点数目非常多，层数很少，目的就是为了就少磁盘IO次数，B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题，由于节点内部每个 key 都带着 data 域，每次查找到具体节点还要和data进行顺序比对，如果查找某个范围内数据，又需要重新遍历。正是为了解决这个问题，B+树应运而生

B树遍历全部数据：

B+Tree

B+树节点只存储 key 的副本，真实的 key 和 data 域都在叶子节点存储，数据全部存储在叶子节，并且每一个节点之间用指针串联起来，形成链表，方便遍历，可以跨区间访问，这优点尤其突出在范围查询，不需要在一次从根节点到子节点遍历。

B+树遍历全部数据：

数据量大的情况下哪个更快，我想你应该知道了吧！

面试 (MySQL 索引为啥要选择 B+ 树)

前言:

每天都在跟 mysql 打交道，你知道执行一条简单的 select 语句，都经历了哪些过程吗？

首先，mysql 主要是由 server 层和存储层两部分构成的。server 层主要包括连接器、查询缓存，分析器、优化器、执行器。存储层主要是用来存储和查询数据的，常用的存储引擎有 InnoDB、MyISAM，MySQL 5.5.5 版本后使用 InnoDB 作为默认存储引擎。

连接器

查询缓存

分析器

优化器

执行器

到这里，一条查询 sql 语句就执行结束了。

开始

在文章正式开始之前，你先要知道 mysql 中的 InnoDB 在底层是采用 B+ 树这种数据结构来存储数据的。你先记住就好了，下面我们再来一步一步解释为什么。

几种常见的数据结构

哈希表

有序数组

二叉搜索树

小结

• 注意，在一些文章中经常会把 B+ 树说成 B 树或者 B-tree，这其实是错误的，B 树和 B+ 是两种不同的树，B+ 树是 B 树的一个优化，后面的文章我会再详细解释这个优化过程。
• 而且 B- 树其实也就是 B 树，这个符号并不是加减中的减号，并不是所谓的 “B 减树”，只是一个连接符号而已。

具体的原因

索引为什么要保存在硬盘中

怎么让二叉搜索树支持区间查询

上面提到过二叉搜索树，为了让二叉搜索树也支持区间查询，我们把二叉树的叶子节点通过一个双向链表来连接，并且这个链表是有序的，注意叶子节点和普通节点是不一样的

如何提升查询速度

那么问题又来了，对于相同的数据量，是不是构建的多叉树的叉越多越好呢，因为叉越多树的高度就会越矮。

插入和删除数据怎么办

上面其实都是为了提高查询性能的，mysql 通常还有插入和删除操作的，这里我们再简单说一下 B+ 树如何处理插入和删除节点的操作。

关于节点分裂和合并操作就简单说这些了，也不画图了，知道这个处理思想就好了。

下面再总结一下 B+ 树：