为什么要用红黑树而不用平衡二叉树_红黑树和b树和b+树的区别

面试官：为什么MySQL 不使用红黑树做索引？ 　　推荐阅读：你知道为什么MySQL用B+树做索引吗？ 　　提到MySQL索引，相信使用过的小伙伴并不陌生，平常工作中，我们经常会加索引来提升查询效率，那么，为什么一个慢查询加上索引查询速度就能提升一个档次？索引后面的实现机制到底是什么？今天就让我们一起来探讨这个话题。 　　1、索引是什么？ 　　比如小学语言，要快速找到某篇课文，我们会通过目录，然后定位到页码，最后再定位到课文。其实，索引就是数据库的“目录”，当你的数据库中的数量达到千万级别时，如果没有这个“目录”，那么要去查找某条数据，那时间肯定会比较漫长，为了能提高查询效率，MySQL提供了索引这样一个机制。 　　2、索引常见的数据结构 　　在日常工作中，用于索引的数据结构常见的有3种：哈希表、有序数组和搜索树。下面给出一张navicat可视化工具创建索引的截图，可以看出它创建索引使用了 BTREE/HASH两种。(截图是navicat连接mysql数据库)

　　2.1、哈希表 　　哈希表是一种以key-value键值对存储数据的结构，比如：java的 hashmap， redis的key-value都是这样一种形式。hash表的实现思路也很简单：用一个哈希函数把 key 换算成数组确定的位置，然后把 value 放在数组的这个位置。

　　从上图我们可以看到，当key的hash值相同的时候，会采用链表的方式把value串起来。 　　hash表的问题随着数据量的增多，不同key经过哈希计算后结果一样，这种情况叫做hash碰撞。处理hash碰撞的一种方法是链表，但是当数据量比较大时，链表的长度还是会比较大，性能开销就在链表查询上。哈希表是散列存储，因此这种结构适用于只有等值查询的场景，比如 Memcached 及其他一些 NoSQL 引擎。 　　2.2、有序数组 　　如下图，如果数据按照id的升序存放到数组中，就形成了一个有序数组，这样既能根据等值查询，也方便范围查询。

　　有序数组问题 如果仅仅看查询效率，有序数组是比较好的数据结构，但如果有数据的插入和删除，插入和删除点后面的数据需要移动，所以整体性能会下降，因此，有序数组只适合静态存储引擎。 　　2.3、搜索树 　　二叉树(Binary Tree) 　　二叉树的定义很简单，它是很多其他搜索树的基础，下面给出一张二叉树的示意图

　　二叉搜索树 　　二叉查找树(Binary Search Tree)，是一种特殊的二叉树，其的特点如下： 　　

　　根据二叉搜索树的特点可以使用二分查找法，比如，在二叉查找树中查询5。 　　首先，从根节点开始遍历，5 > 3，可以定位5在节点3的右子树。 　　其次，遍历节点3的右子树，5 < 6，可以定位 5在节点6的左子树。 　　最后，遍历节点6的左子树，因为左子树只有一个节点5，5=5，即目标值。 　　二叉搜索树的问题 　　当数据是有序增长，极端情况下，整个二叉搜索树就会变成一棵斜树。

　　平衡二叉树 　　平衡二叉树(Balanced Binary Search Tree)，又被称为AVL树，是为了解决二叉树退化成链表而诞生的，其特点如下： 　　为了解决二叉搜索树在极情况下变成斜树的问题，平衡二叉树增加了 左右子树的高度差 小于等于1. 　　问题： 　　平衡二叉树追求绝对严格的平衡，平衡条件必须满足左右子树高度差不超过1，该规则在于频繁的插入、删除等操作的情景性能肯定会出现问题，因此诞生了红黑树。 　　红黑树 　　红黑树是一种特殊的平衡二叉树，主要特点如下： 　　红黑树如下图所示：

　　B-树(Balance Tree) 　　B-树的英文是 Balance Tree，也就是平衡的多路搜索树，它的高度远小于平衡二叉树的高度。在文件系统和数据库系统中的索引结构经常采用 B 树来实现，特点如下： 　　B-树示意图：

　　B+树 　　B+树是基于B-树做了优化，B+树和B-树的差异如下： 　　B+树示意图：

　　上面介绍了常见的搜索树，那么MySQL是使用哪一种树作为索引机制呢？ 　　问题1：为什么MySQL选择B+树做索引而不是其它的树？ 　　MySQL的数据都是存放在磁盘，因此磁盘IO是MySQL的性能瓶颈，而二叉树，二叉搜索树，二叉平衡树，红黑树 都属于二叉树，当MySQL表中的数据量比较大时，索引的体积也会很大，树高就会很大，内存放不下的需要从磁盘读取，树的层次太高的话，读取磁盘的次数就多了，影响MySQL的使用性能。 　　问题2：B+树是怎么实现索引？ 我们从MyISAM和InnoD两个引擎分别讲解 　　MyISAM引擎 　　MyISAM采用的非聚簇索引，B+树的非叶子节点存储索引值和指向子节点的指针，叶子节点上存放的是索引值和数据在磁盘上的物理地址，所以通过索引定位到数据地址后，需要到磁盘上回表数据，索引模型示意图如下：

　　Innodb引擎 　　Innodb采用的聚簇索引(主键索引)，B+树的非叶子节点(内部节点)存放的是索引值和指向子节点的指针，叶子节点上存放的是索引值和数据。 　　非聚簇索引，B+树的非叶子节点存储索引值和指向子节点的指针，叶子节点存放的是索引值和聚簇索引值。因此非聚簇索引需要先遍历非聚簇索引B+树定位到聚簇索引的值，再到聚簇索引上回表数据。 　　聚簇索引的优点：可以避免每棵索引树上都存放数据，使得在相同的内存空间下存放的更多的索引节点，减少磁盘IO。 　　聚簇索引示意图如下：

　　非聚簇索引示意图如下：

　　聚簇索引和非聚簇索引 　　索引覆盖 　　比如上面的案例： 　　select id from user where age = 30 and sex = ‘男’; 　　因为id已经在当前索引的叶子节点，所以不需要到聚簇索引上回表，因此这就是一个索引覆盖的场景。由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。 　　联合索引 　　那么联合索引是如何用B+树实现的呢？ 　　场景：查询用户表中年龄为30岁的男性 　　表结构： 　　联合索引在 B+树索引模型示意图如下：

　　查询分析： 　　首先，从根节点根据组合索引里面的所有字段进行精确匹配查到到age=30 and sex=’男’的记录有两条； 　　然后，id2和id3两个节点中指向子节点的指针，定位到子节点，再定位到叶子节点，从叶子节点中拿到聚簇索引的值 id2和id3； 　　最后，到聚簇索引上遍历id2和id3，直到叶子节点上目标数据； 　　最左前缀原则 　　在日常的工作中，我们发现 查询条件比较多，比如上面的用户表，有根据age和sex查询，有根据name和age查询，也有根据name和sex查询，各种查询组合，那是不是都要为它们创建一个索引呢？ 　　答案是不一定。B+树 可以利用索引的“最左前缀”来定位记录。 　　最左前缀可以是联合索引的最左 N 个字段，也可以是字符串索引的最左 M 个字符 　　比如：联合索引index(a, b, c) 　　查询条件 where a = ? where a = ? and b = ?where a = ? and b = ? and c = ? 　　where 条件中的字段都可以匹配索引，但是 where a = ？and c = ? where条件中的a,c只有a 可以匹配 联合索引的a字段。 　　示例： 　　场景：查询用户表中姓刘的男性 　　联合索引：index(name, sex) 　　B+树索引模型示意图如下：

　　查询分析： 　　首先，从根节点查到第一个’刘’开头的记录是id2，然后向后遍历，直到不满足条件为止，最后结果id2，id3两条； 　　然后，指向子节点的指针，定位到子节点，一直到叶子节点，接着比较第2个字段 sex=’男’，定位到 id2； 　　最后，根据id2到聚簇索引上遍历，直到叶子节点上目标数据； 　　从上面的查询分析可以看到：索引前缀原则，查询条件 name like ‘刘%’ and sex = ‘男’，只用到了联合索引中的name字段，那么set条件没有用到索引会怎么处理呢？ 这个就是MySQL5.6引入的索引下推机制，name字段定位了一批数据减少了全表扫描，在符合name like ‘刘%’的数据集中再筛选sex=’男’，这样减少了回表的次数，降低了磁盘IO。 　　问题3：一个三层的B+树可以存放多少行数据呢？ 　　在Innodb存储引擎里面，最小的存储单是页(page)，一个页的大小是16KB，也就是一个节点的大小。根据上文，非叶子节点保存的是索引值和指针，假设索引id是long类型，占8个byte，指针占6 byte, 所以，根节点可以存放 16KB / (8 + 6) = 1170 个索引值，因此就有1170个指针，假设一条数据的大小是1K，因此叶子节点可以存放 16Kb/1K = 16条数据，所以3层的B+树可以存放 1170 * 1170 * 16 = 行记录 　　LSM-Tree 　　B+树的数据都存储在叶子节点中，而叶子节点一般都存储在磁盘中，我们可以发现B+索引树上相邻的两个节点，其实可能在物理磁盘上不相邻的，因此，每次插入的新数据都需要随机写入磁盘，而磁盘的随机写入的性能非常慢，因此有没有更好的数据结构来解决这个问题？ 　　答案是：LSM-Tree 　　LSM-Tree：Log Structured Merge Trees 日志结构组合树。LSM 树也是近年来许多火热的 NoSQL 数据库中使用的检索技术。比如，日志系统、监控系统。这些应用场景有一个共同的特点：数据会持续地大量生成，而且相比于检索操作，它们的写入操作会非常频繁。另外，即使是检索操作，往往也不是全范围的随机检索，更多的是针对近期数据的检索。 　　LSM-Tree的实现机制 　　LSM-Tree采用的是磁盘顺序写，它是一种多层结构，最上层C0位于内存中，存储最近写入的key-value数据，下面的C1~CN是位于磁盘中，每一层按key的字典顺序进行排序。 　　写操作：先写C0层，当C0层数据达到阈值就会把数据合并到C1层(归并排序)，C1达到阈值，又把数据合并到C2，以此类推。 　　读请求：先读C0层，因为这个层里面的数据是最新的。如果C0没有，则一次往下找。 　　LSM-Tree 示意图

　　使用场景 　　HBase NoSQL数据库，LevelDB 　　通过今天对MySQL 索引机制，我们分析和对比了很多的数据结构，同时我们也会发现，检索是海量数据查询的一个重要课题，针对不同的场景，我们需要采用不同的数据结构。