MySQL为什么选择B+树作为索引结构？ 朱雀 2023-07-11 11:17 78阅读 0赞 ## 各种结构的比较 ## 转自：http://www.gxlcms.com/mysql-366759.html ## 1、平衡二叉树(AVL)：旋转耗时 ## **缺点：由于旋转的耗时，AVL树在删除数据时效率很低** AVL树是严格的平衡二叉树，所有节点的左右子树高度差不能超过1；AVL树查找、插入和删除在平均和最坏情况下都是O(lgn)。 AVL实现平衡的关键在于旋转操作：插入和删除可能破坏二叉树的平衡，此时需要通过一次或多次树旋转来重新平衡这个树。当插入数据时，最多只需要1次旋转(单旋转或双旋转)；但是当删除数据时，会导致树失衡，AVL需要维护从被删除节点到根节点这条路径上所有节点的平衡，旋转的量级为O(lgn)。 在删除操作较多时，维护平衡所需的代价可能高于其带来的好处，因此AVL实际使用并不广泛。 ## 2、红黑树：树太高 ## **优点：对于数据在内存中的情况（如Java的TreeMap和HashMap），红黑树的表现是非常优异的。** **缺点：但是对于数据在磁盘等辅助存储设备中的情况（如MySQL等数据库），红黑树并不擅长，因为红黑树长得还是太高了。** 当数据在磁盘中时，磁盘IO会成为最大的性能瓶颈，设计的目标应该是尽量减少IO次数；而树的高度越高，增删改查所需要的IO次数也越多，会严重影响性能。 与AVL树相比，红黑树并不追求严格的平衡，而是大致的平衡。 与AVL树相比，红黑树的查询效率会有所下降，这是因为树的平衡性变差，高度更高。但红黑树的删除效率大大提高了，因为红黑树同时引入了颜色，当插入或删除数据时，只需要进行O(1)次数的旋转以及变色就能保证基本的平衡。 因此，在实际应用中，AVL树的使用相对较少，而红黑树的使用非常广泛。例如，Java中的TreeMap使用红黑树存储排序键值对；Java8中的HashMap使用链表+红黑树解决哈希冲突问题(当冲突节点较少时，使用链表，当冲突节点较多时，使用红黑树)。 ## 3、B树：为磁盘而生（也叫B-树） ## **优点：** 1. **与二叉树相比，B树的每个非叶节点可以有多个子树。因此，当总节点数量相同时，B树的高度远远小于AVL树和红黑树(B树是一颗“矮胖子”)，磁盘IO次数大大减少。** 2. **B树的优势除了树高小，还有对访问局部性原理（即操作系统的分页存储）的利用。** 所谓局部性原理，是指当一个数据被使用时，其附近的数据有较大概率在短时间内被使用。当一次IO时，不光把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内。 B树将键相近的数据存储在同一个节点，当访问其中某个数据时，数据库会将该整个节点读到缓存中；当它临近的数据紧接着被访问时，可以直接在缓存中读取，无需进行磁盘IO；换句话说，B树的缓存命中率更高。 定义B树最重要的概念是阶数(Order)，对于一颗m阶B树，需要满足以下条件： 1. 每个节点最多包含 m 个子节点。 2. 如果根节点包含子节点，则至少包含 2 个子节点；除根节点外，每个非叶节点至少包含 m/2 个子节点。 3. 拥有 k 个子节点的非叶节点将包含 k - 1 条记录。 4. 所有叶节点都在同一层中。 可以看出，B树的定义，主要是对非叶结点的子节点数量和记录数量的限制。 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70] B树在数据库中有一些应用，如mongodb的索引使用了B树结构。但是在很多数据库应用中，使用了是B树的变种B+树。 ## 4、B+树 ## B+树也是多路平衡查找树，**其与B树的区别主要在于**： 1. **B树中每个节点，包括叶节点和非叶节点，都存储真实的数据，B+树中只有叶子节点存储真实的数据，非叶节点只存储键。** 2. **B树中一条记录只会出现一次，不会重复出现，而B+树的键则可能重复重现——一定会在叶节点出现，也可能在非叶节点重复出现。** 3. **B+树的叶节点之间通过双向链表链接。** B树中的非叶节点，记录数比子节点个数少1；而B+树中记录数与子节点个数相同。 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 1] 这是重点！！！ 由此，B+树与B树相比，**有以下优势**： 1. **更少的IO次数**：B+树的非叶节点只包含键，而不包含真实数据，因此每个节点存储的记录个数比B数多很多（即阶m更大），因此B+树的高度更低，访问时所需要的IO次数更少。此外，由于每个节点存储的记录数更多，所以对访问局部性原理的利用更好，缓存命中率更高。 2. **更适于范围查询**：在B树中进行范围查询时，首先找到要查找的下限，然后对B树进行中序遍历，直到找到查找的上限；而B+树的范围查询，只需要对链表进行遍历即可。 3. **更稳定的查询效率**：B树的查询时间复杂度在1到树高之间(分别对应记录在根节点和叶节点)，而B+树的查询复杂度则稳定为树高，因为所有数据都在叶节点。 **B+树也存在劣势：由于键会重复出现，因此会占用更多的空间**。但是与带来的性能优势相比，空间劣势往往可以接受，因此B+树的在数据库中的使用比B树更加广泛。 ## 5、局部性原理（在意树高的原因） ## 在现代的操作系统中，把数据从外存读到内存所使用的单位一般被称为“页”，每次读取数据都需要读入整数个的“页”，而不能读入半页或者0.8页。一页的大小由操作系统决定，常见的页大小一般为4KB=4096字节。所以不管我们是要读取1字节还是2KB，最后都是需要读入一个完整的4KB大小的页的，那么一个节点的读取成本就取决于需要读入的页数。 在这样的情况下，如果一个节点的大小小于一页的大小，那么就会有一部分时间花在读取我们根本不需要的数据上（节点之外的数据）。 二叉树在这方面就会浪费很多时间，其一个节点中只有一个数据，每次IO只能得到一个有用数据，而如果一个节点中包含的数据越多，一次IO中有用数据越多，效率就会大大提升。 [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200305123036516.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA==,size_16,color_FFFFFF,t_70 [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020030512301587.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc1MTcxMA==,size_16,color_FFFFFF,t_70
还没有评论，来说两句吧...