Mysql为什么采用B+树

Mysql为什么采用B 树

Mysql为什么选则树结构？

众多的数据结构中我们可以分为：线性结构和非线性结构。
线性结构主要有：数组、链表、基于它们衍生出的有哈希表、栈、队列等。
非线性结构有：树、图。
还有其他的数据结构：跳表、位图也都是由基础的数据结构演化而来的，不同的数据结构存在即都是为了解决某些场景问题。
我们思考mysql索引适合什么样数据结构，首先应该思考索引是用来解决什么样的问题？索引发挥着什么样的作用？然后再思考什么样的数据结构能够解决这样的问题，实现这样的作用。
mysql存储的数据是在磁盘里的，即使设备断电，放在磁盘里面的数据是不会有影响的，保证了数据不丢失，也就是说Mysql在磁盘上的数据是持久化的。
但是数据存储在磁盘得到保障的同时也是有代价的，代价就是磁盘的处理速度是毫秒级别的，而内存的处理速度是纳秒级别的。相比存储在内存的性能要差很多。
索引虽然存储在磁盘上，但是使用索引查找数据时，可以从磁盘先读取索引放到内存中，再通过索引从磁盘找到数据；再然后将磁盘读取到的数据也放到内存里。（由于索引存在内存中，而索引又能快速的确定数据的位置，因此性能会得到很大的提升。）
但是不管查询过程中怎么优化，只要根还在磁盘，就避免不了会发生多次磁盘I/O，而磁盘I/O次数越多，消耗的时间也越多。（因此在选择索引的数据结构时，要考虑尽量少的磁盘I/O）。
因此选择索引主要要满足两个要求：

• 要尽量少在磁盘做I/O操作。
• 要能尽快的按照区间高效地范围查找。
  当然索引首要目的能支持高效范围查询，还要有插入更新等操作的动态数据结构。
  所以有满足以这两条主要条件的除了树结构你还会想到其他什么数据结构？
  哈希表、跳表

哈希表

哈希表的物理存储是一个数组，而数组在内存中是连续地址的空间。数据以key、value的方式存储。所以哈希表拥有精确的查询，时间复杂度为o(1)；
哈希表之所以能这么快是通过key计算数组下标来快速找到value。最简单的计算方式是余数法，通过先计算key的hashcode，再通过哈希表的数组长度对hashcode求余，求余得出的余数就是数组下标，最后由下标访问到表中存的key，value。

但是key计算出的下标可能会有相同的情况，这种情况就是哈希冲突，解决哈希冲突的两种方法就是拉链法和线性探查法。
哈希表可以高效的进行等值查询。例如：

select * from table where username="name";

但是哈希表就不适合做区间查询。例如：

select * from where age>18;

如果使用哈希表来做索引，当进行范围查询时，就需要全部扫描。

跳表

再看跳表，跳表是再Redis中比较常用的数据结构之一，跳表的底层实质就是可以进行二分查找的有序链表。而且在链表基础上加上索引层，即能支持插入、删除等动态操作，也支持按区间高效查询。而且不管是查找、插入、删除对应的时间复杂度都是O(logn)。
普通的链表形式如下：

在查找的时候链表的时间复杂度为O(n)，相对与数组来说要慢，因此可以采用空间换时间的策略给链表加索引。如图：

如果查找18这个值，普通链表需要比较八次，但是在上一层建立索引后就只需要比较5次，也可以在更上一层再建立索引以减少比较次数。总结一下就是：加一层索引，查询所需要遍历的节点个数减少，查询效率也就提高了。
看到这，跳表好像也很适合用来作为索引的数据结构。但是对于数据库来说，还有一个条件没有满足，就是要尽量少做磁盘I/O。而跳表显然不满足条件，跳表在随着数据增多的情况下，索引也会随着增高，相应的就会增加读取I/O的次数，从而影响性能。
最后再看为什么选用树结构。

树结构

从树结构的层级角度看，其实树结构是不是跟前面的跳表还有点相似。而跳表之所以这么快是因为有能按区间高效查询的索引层。
而树结构其特性决定了遍历数据方式本身就纯天然的支持按区间查询。再加上树是非线性结构的优势相比于线性结构的数组，不必像数组的数据是连续存放的。那么当树结构在插入新数据时就不用像数组插入数据前时，需要将数据所在往后的所有数据节点都得往后挪动的开销。所以树结构更适合插入更新等动态操作的数据结构。
树结构在满足了索引目的和其他条件的情况下，至于减少磁盘查询操作的痛点其实我们就可以在基于树结构的数据结构中去选择。

那么多树结构，为什么使用B 树作为索引?

二叉树

在了解二叉树或者平衡二叉树前需要先简单知道什么是二叉树，什么是二分查找树。因为你看二叉查找树 不就是这两棵树的合并吗。
我们先来看看二叉树，二叉树的树结构中定义的是每个节点的可以是0个子节点或1个子节点，但是最多不超过2个子节点。
而二叉树还有两个形式：满二叉树、完全二叉树

满二叉树

满二叉树的定义是一颗二叉树的所有非叶子节点都存在左右子节点，并且所有子节点在同一级。

完全二叉树

完全二叉树的定义是如果这颗树的所有节点和同深度的满二叉树的的节点位置相同则这二叉树是完全二叉树。

二叉查找树

二叉查找树(Binary Search Tree，BST)，又叫做二叉排序树、二叉搜索树，是一种对查找和排序都有用的特殊二叉树。
二叉查找树或是空树，或是满足如下三个性质的二叉树：

• 若其左子树非空，则左子树上所有节点的值都小于根节点的值
• 若其右子树非空，则右子树上所有节点的值都大于根节点的值
• 其左右子树都是一棵二叉查找树
  二叉查找树的特性：左子树<根<右子树，即二叉查找树的中序遍历是一个递增序列。
  
  二分查找树在查找数据时，只需要将需要查找的元素与树节点元素进行比较，当元素大于根节点则往右子树中查找，元素小于根节点则往左子树中查找，元素如果正好是中位数那么就是正好是根节点，所以二叉查找树具备高效查询。
  但是二叉树也有明显弊端，在极端情况下，如果每次插入的数据都是最小或者都是最大的元素，那么树结构会退化成一条链表。查询数据是的时间复杂度就会是O(n)

平衡二叉树

平衡二叉树，又称为AVL树。实际上就是遵循以下两个特点的二叉树：

• 每棵子树中的左子树和右子树的深度差不能超过 1；
• 二叉树中每棵子树都要求是平衡二叉树；

不平衡的二叉树：

平衡二叉树：

当然还有在 Java中集合类常见的红黑树，也是平衡二叉树中的一种。

但是不管自平衡树是平衡二叉查找树还是红黑树，都会随着插入的元素增多，而导致树的高度变高，这同样意味着磁盘 I/O 操作次数多，影响到整体查询的效率。

B树

MySQL的数据是存储在磁盘文件中的，查询处理数据时，需要先把磁盘中的数据加载到内存中，磁盘IO 操作非常耗时，所以我们优化的重点就是尽量减少磁盘 IO 操作。访问二叉树的每个节点就会发生一次IO，如果想要减少磁盘IO操作，就需要尽量降低树的高度。那如何降低树的高度呢？

假如key为bigint=8字节，每个节点有两个指针，每个指针为4个字节，一个节点占用的空间16个字节（8 4*2=16）。

因为在MySQL的InnoDB存储引擎一次IO会读取的一页（默认一页16K）的数据量，而二叉树一次IO有效数据量只有16字节，空间利用率极低。为了最大化利用一次IO空间，一个简单的想法是在每个节点存储多个元素，在每个节点尽可能多的存储数据。每个节点可以存储1000个索引（16k/16=1000），这样就将二叉树改造成了多叉树，通过增加树的叉树，将树从高瘦变为矮胖。构建1百万条数据，树的高度只需要2层就可以（1000*1000=1百万），也就是说只需要2次磁盘IO就可以查询到数据。磁盘IO次数变少了，查询数据的效率也就提高了。
这种数据结构我们称为B树，B树是一种多叉平衡查找树，如下图主要特点：

• B树的节点中存储着多个元素，每个内节点有多个分叉。
• 节点中的元素包含键值和数据，节点中的键值从大到小排列。也就是说，在所有的节点都储存数据。
• 父节点当中的元素不会出现在子节点中。
• 所有的叶子结点都位于同一层，叶节点具有相同的深度，叶节点之间没有指针连接。
• 
  看到这里可能会觉得B树就比较理想了，但是还是存在可以优化的地方。
• B树不支持范围查询的快速查找，你想想这么一个情况如果我们想要查找10和35之间的数据，查找到15之后，需要回到根节点重新遍历查找，需要从根节点进行多次遍历，查询效率有待提高。
• 如果data存储的是行记录，行的大小随着列数的增多，所占空间会变大。这时，一个页中可存储的数据量就会变少，树相应就会变高，磁盘IO次数就会变大。

B 树

B 树，作为B树的升级版，在B树基础上，MySQL在B树的基础上继续改造，使用B 树构建索引。B 树和B树最主要的区别在于非叶子节点是否存储数据的问题

• B树：非叶子节点和叶子节点都会存储数据。
• B 树：只有叶子节点才会存储数据，非叶子节点至存储键值。叶子节点之间使用双向指针连接，最底层的叶子节点形成了一个双向有序链表。
  

B 树的最底层叶子节点包含了所有的索引项。从图上可以看到，B 树在查找数据的时候，由于数据都存放在最底层的叶子节点上，所以每次查找都需要检索到叶子节点才能查询到数据。所以在需要查询数据的情况下每次的磁盘的IO跟树高有直接的关系，但是从另一方面来说，由于数据都被放到了叶子节点，所以放索引的磁盘块所存放的索引数量是会跟着增加的，所以相对于B树来说，B 树的树高理论上情况下是比B树要矮的。也存在索引覆盖查询的情况，在索引中数据满足了当前查询语句所需要的全部数据，此时只需要找到索引即可立刻返回，不需要检索到最底层的叶子节点。

总结

哈希表单值查询时效率较高，但是不适合范围查询。
跳表的高度过高，会导致大量的磁盘I/O操作。
B树在范围查询时，需要重复的访问根，会有更多的磁盘I/O。
B 树只在叶子存储数据，并且叶子节点间为双向链表，可以减少I/O，因此选择B 树。

这篇好文章是转载于：学新通技术网