MySQL底层数据结构应用的变化及比较

  • 时间:
  • 浏览:
  • 来源:互联网

MySQL底层数据结构应用的变化及比较

我们知道的数据结构有很多,下面列出了5种。
Hash (HashMap种使用较多)
二叉树
平衡二叉树
B 树
B+ 树

既然有这么多种,为什么又刚好选择了B + 树作为存储结构呢?

1、为什么不是用hash 作为存储结构?
Hash在HashMap中得到了充分体现,数组 + 链表 + (JDK 1.8)红黑树,经过多次修改,检索效率是非常高的,时间复杂度为 O( 1 ),但是,数据一多,时间复杂度就变成了O( n ),这样看来,对于存储千万数据的MySQL显然是不够用的。

2、为什么不用二叉树作为存储结构?
这个就很简单了,缺点很明显,一边倒的性质,万一都在同一边,你还觉得它的效率高吗?

3、为什么不用平衡二叉树? o(log2 n)
平衡二叉树 通俗的理解就是两边平衡嘛,刚好解决了二叉树一边倒的问题,它的查找的最多次数和树的高度有关,可想而知,在树的高度达到一定程度的时候,查找效率还是会有所下降。

4、为什么不用b树?
B树,很多不了解数据结构的人可能不是很了解,我这里就概括一下,B树就相当于一颗升级版的平衡二叉树,它可以作为 2 - 3 - 4树,也就是一个结点可以存放 2 个或者是 3 个数据。
在这里插入图片描述

b树通过,压缩树的高度,也就是说不仅仅是二叉树,变成了三叉树的情况,也就是所谓的二三树,每个节点不止存放一个数据,这样一来树的高度也就大大降低了,按理来说这样已经优化的很好了,为什么又用到了B+树呢?

首先就是查询范围的效率,b树在查询范围的时候需要使用到中需遍历,左根右,一个一个去遍历需要的数据。

接下来就是MySQL默认的存储结构了
在这里插入图片描述
从上图可以看得到,B+树使用链表结构,将数据串起来,也就是使用了树加链表的结构,这样一来就解决了范围i查询的问题(一种数据结构无法做到最优,就可以整合其他优良的一起优化,像hashmap一样,使用的是数组 + 链表 + 红黑树的结构 这种思想我觉得是我们每一个程序员都需要学习的,毕竟时代发展快,各种基础层出不穷,我们需要选最优的来进行操作)
还有一个很重要的一点
B+ 树 有一个很大的优点,所有结点都会在叶子节点出现,也就是说冗余了一份,并且 每一部分之间有双向链表相连,这样一来,查询范围的情况就很容易查询出来。
B+树中,在主键索引,聚集索引中,只有在叶子结点才会存放数据,这样一来就减少了IO的次数,性能也就提升很多。

总结的感觉真香

本文链接http://xiahunao.cn/article/show-994409.html