深圳服务好的网站建设,营销策划与运营方案,软件开发工具的根本功能,网络工程专业就业前景前言在MySQL中#xff0c;无论是Innodb还是MyIsam#xff0c;都使用了B树作索引结构(这里不考虑hash等其他索引)。本文将从最普通的二叉查找树开始#xff0c;逐步说明各种树解决的问题以及面临的新问题#xff0c;从而说明MySQL为什么选择B树作为索引结构。目录一、二叉查…前言在MySQL中无论是Innodb还是MyIsam都使用了B树作索引结构(这里不考虑hash等其他索引)。本文将从最普通的二叉查找树开始逐步说明各种树解决的问题以及面临的新问题从而说明MySQL为什么选择B树作为索引结构。目录一、二叉查找树(BST)不平衡二、平衡二叉树(AVL)旋转耗时三、红黑树树太高四、B树为磁盘而生五、B树六、感受B树的威力七、总结一、二叉查找树(BST)不平衡二叉查找树(BSTBinary Search Tree)也叫二叉排序树在二叉树的基础上需要满足任意节点的左子树上所有节点值不大于根节点的值任意节点的右子树上所有节点值不小于根节点的值。如下是一颗BST(图片来源)。当需要快速查找时将数据存储在BST是一种常见的选择因为此时查询时间取决于树高平均时间复杂度是O(lgn)。然而BST可能长歪而变得不平衡如下图所示(图片来源)此时BST退化为链表时间复杂度退化为O(n)。为了解决这个问题引入了平衡二叉树。二、平衡二叉树(AVL)旋转耗时AVL树是严格的平衡二叉树所有节点的左右子树高度差不能超过1AVL树查找、插入和删除在平均和最坏情况下都是O(lgn)。AVL实现平衡的关键在于旋转操作插入和删除可能破坏二叉树的平衡此时需要通过一次或多次树旋转来重新平衡这个树。当插入数据时最多只需要1次旋转(单旋转或双旋转)但是当删除数据时会导致树失衡AVL需要维护从被删除节点到根节点这条路径上所有节点的平衡旋转的量级为O(lgn)。由于旋转的耗时AVL树在删除数据时效率很低在删除操作较多时维护平衡所需的代价可能高于其带来的好处因此AVL实际使用并不广泛。另外最新 Java 和数据结构面试题整理好了点击Java面试库小程序在线刷题。三、红黑树树太高与AVL树相比红黑树并不追求严格的平衡而是大致的平衡只是确保从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。从实现来看红黑树最大的特点是每个节点都属于两种颜色(红色或黑色)之一且节点颜色的划分需要满足特定的规则(具体规则略)。红黑树示例如下图片来源与AVL树相比红黑树的查询效率会有所下降这是因为树的平衡性变差高度更高。但红黑树的删除效率大大提高了因为红黑树同时引入了颜色当插入或删除数据时只需要进行O(1)次数的旋转以及变色就能保证基本的平衡不需要像AVL树进行O(lgn)次数的旋转。总的来说红黑树的统计性能高于AVL。因此在实际应用中AVL树的使用相对较少而红黑树的使用非常广泛。例如Java中的TreeMap使用红黑树存储排序键值对Java8中的HashMap使用链表红黑树解决哈希冲突问题(当冲突节点较少时使用链表当冲突节点较多时使用红黑树)。对于数据在内存中的情况如上述的TreeMap和HashMap红黑树的表现是非常优异的。但是对于数据在磁盘等辅助存储设备中的情况如MySQL等数据库红黑树并不擅长因为红黑树长得还是太高了。当数据在磁盘中时磁盘IO会成为最大的性能瓶颈设计的目标应该是尽量减少IO次数而树的高度越高增删改查所需要的IO次数也越多会严重影响性能。四、B树为磁盘而生B树也称B-树(其中-不是减号)是为磁盘等辅存设备设计的多路平衡查找树与二叉树相比B树的每个非叶节点可以有多个子树。 因此当总节点数量相同时B树的高度远远小于AVL树和红黑树(B树是一颗“矮胖子”)磁盘IO次数大大减少。定义B树最重要的概念是阶数(Order)对于一颗m阶B树需要满足以下条件每个节点最多包含 m 个子节点。如果根节点包含子节点则至少包含 2 个子节点除根节点外每个非叶节点至少包含 m/2 个子节点。拥有 k 个子节点的非叶节点将包含 k - 1 条记录。所有叶节点都在同一层中。可以看出B树的定义主要是对非叶结点的子节点数量和记录数量的限制下图是一个3阶B树的例子图片来源B树的优势除了树高小还有对访问局部性原理的利用。所谓局部性原理是指当一个数据被使用时其附近的数据有较大概率在短时间内被使用。B树将键相近的数据存储在同一个节点当访问其中某个数据时数据库会将该整个节点读到缓存中当它临近的数据紧接着被访问时可以直接在缓存中读取无需进行磁盘IO换句话说B树的缓存命中率更高。B树在数据库中有一些应用如mongodb的索引使用了B树结构。但是在很多数据库应用中使用了是B树的变种B树。五、B树B树也是多路平衡查找树其与B树的区别主要在于B树中每个节点包括叶节点和非叶节点都存储真实的数据B树中只有叶子节点存储真实的数据非叶节点只存储键。在MySQL中这里所说的真实数据可能是行的全部数据如Innodb的聚簇索引也可能只是行的主键如Innodb的辅助索引或者是行所在的地址如MyIsam的非聚簇索引。B树中一条记录只会出现一次不会重复出现而B树的键则可能重复重现——一定会在叶节点出现也可能在非叶节点重复出现。B树的叶节点之间通过双向链表链接。B树中的非叶节点记录数比子节点个数少1而B树中记录数与子节点个数相同。由此B树与B树相比有以下优势更少的IO次数B树的非叶节点只包含键而不包含真实数据因此每个节点存储的记录个数比B数多很多即阶m更大因此B树的高度更低访问时所需要的IO次数更少。此外由于每个节点存储的记录数更多所以对访问局部性原理的利用更好缓存命中率更高。更适于范围查询在B树中进行范围查询时首先找到要查找的下限然后对B树进行中序遍历直到找到查找的上限而B树的范围查询只需要对链表进行遍历即可。更稳定的查询效率B树的查询时间复杂度在1到树高之间(分别对应记录在根节点和叶节点)而B树的查询复杂度则稳定为树高因为所有数据都在叶节点。B树也存在劣势由于键会重复出现因此会占用更多的空间。但是与带来的性能优势相比空间劣势往往可以接受因此B树的在数据库中的使用比B树更加广泛。六、感受B树的威力前面说到B树/B树与红黑树等二叉树相比最大的优势在于树高更小。实际上对于Innodb的B索引来说树的高度一般在2-4层。下面来进行一些具体的估算。树的高度是由阶数决定的阶数越大树越矮而阶数的大小又取决于每个节点可以存储多少条记录。Innodb中每个节点使用一个页(page)页的大小为16KB其中元数据只占大约128字节左右(包括文件管理头信息、页面头信息等等)大多数空间都用来存储数据。对于非叶节点记录只包含索引的键和指向下一层节点的指针。假设每个非叶节点页面存储1000条记录则每条记录大约占用16字节当索引是整型或较短的字符串时这个假设是合理的。延伸一下我们经常听到建议说索引列长度不应过大原因就在这里索引列太长每个节点包含的记录数太少会导致树太高索引的效果会大打折扣而且索引还会浪费更多的空间。对于叶节点记录包含了索引的键和值(值可能是行的主键、一行完整数据等具体见前文)数据量更大。这里假设每个叶节点页面存储100条记录(实际上当索引为聚簇索引时这个数字可能不足100当索引为辅助索引时这个数字可能远大于100可以根据实际情况进行估算)。对于一颗3层B树第一层(根节点)有1个页面可以存储1000条记录第二层有1000个页面可以存储10001000条记录第三层(叶节点)有10001000个页面每个页面可以存储100条记录因此可以存储10001000100条记录即1亿条。而对于二叉树存储1亿条记录则需要26层左右。七、总结最后总结一下各种树解决的问题以及面临的新问题二叉查找树(BST)解决了排序的基本问题但是由于无法保证平衡可能退化为链表平衡二叉树(AVL)通过旋转解决了平衡的问题但是旋转操作效率太低红黑树通过舍弃严格的平衡和引入红黑节点解决了AVL旋转效率过低的问题但是在磁盘等场景下树仍然太高IO次数太多B树通过将二叉树改为多路平衡查找树解决了树过高的问题B树在B树的基础上将非叶节点改造为不存储数据的纯索引节点进一步降低了树的高度此外将叶节点使用指针连接成链表范围查询更加高效。
