数据结构学习——B-树 & B+树 一、概述 1.B-树 B-树其实就是B树（多路平衡查找树），我们之前学习的234树其实就是B-树的一种，234树是一种4阶B-树。m阶B-树，每个节点拥有最多不超过m-1个数据，每个节点拥有最多不超过m个孩子节点。因为之前我们已经对234树进行了详细介绍本文就不在对B-树做详细介绍了。数据结构学习——2-3-4树 2.B+树 B+树是B-树的一种改进，大部分性质与B-树相同，不同的是B+树所有数据都在叶子节点上，内部节点只存储索引（索引在仅有value的B+树结构中索引就是value，在key-value的结构树中，索引是key）。又因为B+树所有数据都在叶子节点上，因此B+树每个叶子节点与相邻的叶子节点可以是相互连接的，可以是双链也可以是单链还可以是环单环双环等。所以B+树对于批量查询很友好，比如查询大于n的所有数据，我们只需要找到n数据所在位置就可以很方面的拿到后面的数据。
B+树 二、添加 1.B-树 B-树的添加基本上与234树是一致。分裂时，左子树包含前(m-1)/2个，父节点为第(m-1)/2+1个，右子树包含后面m-(m-1)/2-1个。 2.B+树 B+树的添加数据与B-树基本一致，不同的是，在分裂时，左子树包含前(m-1)/2，父节点为第(m-1)/2+1个的索引，右子树包含m-(m-1)/2个。 三、删除 1.B-树 B-树的删除基本上与234树的一致。若删除数据在分支节点上需要将数据替换到叶子节点，然后执行以下操作。若删除数据在叶子节点上直接执行下述操作即可。删除数据所在节点数据个数大于 1个，直接删除即可。(234树直接删除)删除数据所在节点数据个数只有1个，但兄弟节点大于1个，执行旋转操作，使删除数据所在节点数据个数大于1个，然后删除数据即可。(234树旋转删除)删除数据所在节点以及兄弟节点的数据个数都小于1个，但父节点大于1个，将父节点对应位置的数据下移与兄弟节点和自己合并成一个新的节点，然后删除数据即可。(234树向下合并删除)删除数据所在节点以及兄弟节点和父节点数据个数都只有1个，兄弟节点与父节点和自己合并成一个新的节点，然后删除数据即可。(234树的向上合并删除)若需要树高的绝对平衡，则删除数据所在节点以及兄弟节点和父节点数据个数都只有1个时，应当通过旋转或向下合并等操作向更上级节点获得数据，使删除数据所在节点的数据个数大于1个。(参考234树删除说明) 说明：上述数据个数边界都为1个，实际为了数据的更为平衡可以将数据个数的边界设置为Math.ceil(m-1)/2–1，即数据个数的一半减去1个。 2.B+树 B+树的删除基本上与B-树一致，但值得一提的是，B+树的所有数据都在叶子节点上，因此不存在删除分支节点上的数据这种情况，因此删除操作会简单许多。 四、区别 若所有数据都存储在内存中，B-树查询效率会高一点，因为不是所有数据都在叶子节点上，最好O(1)就能拿到结果。若所有数据都存储在磁盘上，B+树查询效率更高，因为B+树的内部节点只有索引值，但B-树的内部节点不仅有索引值还有value数据IO消耗更多。若做区域查询，B+树效率更高，因为所有数据都在叶子节点上且相邻的叶子节点相互连接，只需要找个一个节点位置就能很容易拿到其他数据。插入效率，B-树效率更高，B+树比B-树多了索引，插入数据需要执行更多的操作且更容易发生分裂。 附录 其他学习内容 算法&数据结构学习内容
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/18858.html
