MySQL_索引树

查看树插入删除图解：

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

时间复杂度：O(N)

时间复杂度：O(logn)

如果数据插入是递增或者递减顺序的话，会使树成为链式结构。 时间复杂度：O(N)

为了保证平衡，在插入或者删除的时候必须要旋转，通过插入或者删除性能的损失来弥补查询性能的提升。

但如果写请求和读请求一样多的时候怎么办？

随着数据的插入，树的深度会变深，树的深度越深，意味着 IO 次数越多。影响数据读取的效率。

MySQL 的页大小是16k。假设只有data 占用空间且占用 1k 一个磁盘块可以放置16条记录，三层就是 4096条记录。肯定小于 4096.

如果想要放入更多的数据的化，得加层。加层 IO 量肯定上来了。

data 太占内存，导致存储数据太少。

MySQL加载索引是以磁盘块（页）为单位的，页（Page）是 Innodb 存储引擎用于管理数据的最小磁盘单位。默认的页大小为 16KB。

假设只有 p1+key 值 占用空间且占用 10字节， 一个磁盘块可以放置1600条记录，三层就是 40960000条记录。

在B+树 上有两个头节点，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有的叶子节点（即数据节点）之间是一种链式环结构，因此可以对 B+树 进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。

让当前key值尽可能的少占用存储空间，才能保证存储更多的值。降低树的高度，减少IO。

保证key的长度越小越好。

为什么Mysql考虑使用B+树，而不是B树，其实我们可以先了解下B树和B+树的特点来看下。

※ 树的每个结点都会存储数据

※ 单次查询不一定要遍历到树的根部，平均查询时间会比较快

※ 非叶子节点不存储数据，只存储（冗余）索引，索引包含主键和指针

※ 叶子节点才真正存储数据

※ 每个叶子节点互相链表相连，保证了范围查询的时效性(页之间用双向链表连接，数据间用单项链表链接)

InnoDB最小存储单位是页，叶子节点和非叶子节点最小单位都是页，页大小Mysql 默认设定16384字节，约为16KB。

我们假设主键ID为bigint类型，长度为8字节，而指针大小在InnoDB源码中设置为6字节，这样一共14字节

我们一个页中能存放多少这样的索引元素，其实就代表有多少指针，即16384/14=1170

高度为2的B+树能存放1170×16=18720

高度为3的B+树能存放1170×1170×16 = 21902400

InnoDB中B+树高度一般为1-3层，它就能满足千万级的数据存储。

在查找数据时一次页的查找代表一次IO，所以通过主键索引查询通常只需要1-3次IO *** 作即可查找到数据。

面试时候经常会被问到mysql的索引结构，B+树相较二叉树，红黑树的优势等问题，接下来就分析下这些问题。

首先，让我们先看一张图：

从图中可以看到，我们为 user 表（用户信息表）建立了一个二叉查找树的索引。

图中的圆为二叉查找树的节点，节点中存储了键（key）和数据（data）。键对应 user 表中的 id，数据对应 user 表中的行数据。

二叉查找树的特点就是任何节点的左子节点的键值都小于当前节点的键值，右子节点的键值都大于当前节点的键值。顶端的节点我们称为根节点，没有子节点的节点我们称之为叶节点。

如果我们需要查找 id=12 的用户信息，利用我们创建的二叉查找树索引，查找流程如下：

利用二叉查找树我们只需要 3 次即可找到匹配的数据。如果在表中一条条的查找的话，我们需要 6 次才能找到。

上面我们讲解了利用二叉查找树可以快速的找到数据。但是，如果上面的二叉查找树是这样的构造：

这个时候可以看到我们的二叉查找树变成了一个链表。如果我们需要查找 id=17 的用户信息，我们需要查找 7 次，也就相当于全表扫描了。 导致这个现象的原因其实是二叉查找树变得不平衡了，也就是高度太高了，从而导致查找效率的不稳定。为了解决这个问题，我们需要保证二叉查找树一直保持平衡，就需要用到平衡二叉树了。 平衡二叉树又称 AVL 树，在满足二叉查找树特性的基础上，要求每个节点的左右子树的高度差不能超过 1。

下面是平衡二叉树和非平衡二叉树的对比：

由平衡二叉树的构造我们可以发现第一张图中的二叉树其实就是一棵平衡二叉树。

平衡二叉树保证了树的构造是平衡的，当我们插入或删除数据导致不满足平衡二叉树不平衡时，平衡二叉树会进行调整树上的节点来保持平衡。具体的调整方式这里就不介绍了。平衡二叉树相比于二叉查找树来说，查找效率更稳定，总体的查找速度也更快。

因为内存的易失性。一般情况下，我们都会选择将 user 表中的数据和索引存储在磁盘这种外围设备中。但是和内存相比，从磁盘中读取数据的速度会慢上百倍千倍甚至万倍，所以，我们应当尽量减少从磁盘中读取数据的次数。另外，从磁盘中读取数据时，都是按照磁盘块来读取的，并不是一条一条的读。如果我们能把尽量多的数据放进磁盘块中，那一次磁盘读取 *** 作就会读取更多数据，那我们查找数据的时间也会大幅度降低。如果我们用树这种数据结构作为索引的数据结构，那我们每查找一次数据就需要从磁盘中读取一个节点，也就是我们说的一个磁盘块。我们都知道平衡二叉树可是每个节点只存储一个键值和数据的。那说明什么？说明每个磁盘块仅仅存储一个键值和数据！那如果我们要存储海量的数据呢？

可以想象到二叉树的节点将会非常多，高度也会极其高，我们查找数据时也会进行很多次磁盘 IO，我们查找数据的效率将会极低！

为了解决平衡二叉树的这个弊端，我们应该寻找一种单个节点可以存储多个键值和数据的平衡树。也就是我们接下来要说的 B 树。

B 树（Balance Tree）即为平衡树的意思，下图即是一棵 B 树：

图中的 p 节点为指向子节点的指针，二叉查找树和平衡二叉树其实也有，因为图的美观性，被省略了。

图中的每个节点称为页，页就是我们上面说的磁盘块，在 MySQL 中数据读取的基本单位都是页，所以我们这里叫做页更符合 MySQL 中索引的底层数据结构。

从上图可以看出，B 树相对于平衡二叉树，每个节点存储了更多的键值（key）和数据（data），并且每个节点拥有更多的子节点，子节点的个数一般称为阶，上述图中的 B 树为 3 阶 B 树，高度也会很低。

基于这个特性，B 树查找数据读取磁盘的次数将会很少，数据的查找效率也会比平衡二叉树高很多。

假如我们要查找 id=28 的用户信息，那么我们在上图 B 树中查找的流程如下：

B+ 树是对 B 树的进一步优化。让我们先来看下 B+ 树的结构图：

根据上图我们来看下 B+ 树和 B 树有什么不同：

通过上图可以看到，在 InnoDB 中，我们通过数据页之间通过双向链表连接以及叶子节点中数据之间通过单向链表连接的方式可以找到表中所有的数据。

MyISAM 中的 B+ 树索引实现与 InnoDB 中的略有不同。在 MyISAM 中，B+ 树索引的叶子节点并不存储数据，而是存储数据的文件地址。

摘自： http://www.liuzk.com/410.html

---