为什么 MySQL 选择 B＋树作为存储引擎索引结构( 五 )

那上述问题我们也就进一步延伸到了，采用哪种数据结构来组织我们的数据，并尽可能使得其读写比较快速、高效。具体的快速、高效通过时间复杂度来判定。
2.3 总结
本小节我们对前面介绍的两部分内容通过一个框图来进行总结回顾。具体的选择哪种数据结构这个问题我们放到下一节来进行介绍。

本文插图
3.数据结构选型
在2.2节提到，我们最终将
快速、高效读写
这个问题转化成了
选择采用哪种数据结构来组织数据、并通过其时间复杂度来定量的判定我们的目标
。下面我们就从数据结构这个方面着手看看。
3.1 数据结构方案对比
我们详细的分析下，
快速、高效
那也就意味着读写的平均时间复杂度，要尽可能的低。在数据结构中我们学习过很多的数据结构，例如：平均时间复杂度是 O(1) 的数据结构，典型代表是哈希表(hash table) 。哈希表主要在点对点的映射读写上冲突比较低时效率很高，但其原生的数据结构在面对范围查找、排序等操作时时间复杂度会相对较高，这也算是哈希表的一大缺陷；其次平均时间复杂度比 O(1) 稍慢的是平均时间复杂度为 O(logn) ，这类数据结构有二叉查找/排序树(bst tree)、平衡二叉树(avl tree)、红黑树(rb tree)、B 树(b/b- tree)、B+ 树(b+ tree)、跳表(skiplist)等。他们天然就支持排序、范围查找操作；再其次比 O(logn) 还慢的时间复杂度为O(n)、O(n2)等等。 O(n) 的平均时间复杂度的典型代表有数组。其他类型我们这儿就不过多展开了。
下图是我们根据平均时间复杂度依次从
O(1)->O(logn)->O(n)->...
由快到慢的一个对比结果。

本文插图
我们都知道互联网的应用中，排序、范围查找是一个再普遍不过的需求了。例如在电商网站购物时，大部分用户都会下意识的点击按照销量从高到低排序；再比如在门户新闻网站上，我们会关注过去一周某个新闻被阅读的次数，按照时间来排序；再比如推荐系统中，我们会按照内容的一类或者多类属性对物品进行排序，还有很多很多例子。所以我们在选择数据结构时，必须考虑
支持范围查找、排序等操作
。
基于这点的话，看来哈希表就不太符合我们的需求了。那我们退而求其次，再来看看 O(logn)的时间复杂度中，我们选择哪种数据结构呢？这几种数据结构粗略一看貌似都能满足我们的需求，同时上述几种数据结构:
二叉查找/排序树(bst tree)、平衡二叉树(avl tree)、红黑树(rb tree)、B 树(b/b- tree)、B+ 树(b+ tree)、跳表(skiplist)