概述
- 234树是4阶的B树，是一种自平衡的数据结构，查找效率为O(logN)。
- 234树和二叉查找树一样，2节点满足左子树中所有key一定小于当前节点中key，右子树中的所有key一定大于当前节点的key。
- 每个3，4节点的key保持从小到大的顺序，两个相邻key之间的子树中所有的key一定大于它的父节点的左key，小于父节点的右key。
- 234中的节点一定是2，3，4三种节点，这个是B树的通用特性：
- m阶的B树中，节点中key最多为m-1，最少为[m/2] -1（m/2向上取整，比如1.5取2）
- 所有叶子节点到根节点的深度一致，也就是说所有叶子节点一定在同一层。
添加操作
添加操作相对简单：
原则是从叶子节点插入，如果节点中的key超过3个，分裂中间节点，分裂后的中间节点和同一层的兄弟节点合并。
- 如果树中已经存在待插入的key，则插入失败，否则最终的插入位置，一定是在叶子节点中进行插入操作。
- 如果待插入的节点不是4节点，那么直接插入到该节点中即可。
- 如果待插入的节点是4节点，那么应该先分裂该节点然后插入。四节点分裂成一个根和作用两个子节点，然后在子节点中插入，我们把分裂形成的根节点中的key看成向上层插入的key，然后重复2,3两步。
通过7,9,11,13,16,18,20,22,24,29生成一颗234树中
- 依次插入生成一个4节点
- 插入13
- 插入18
- 最后插入29的过程
删除操作
- 如果234树中不存在当前需要删除的key，删除失败。
- 如果当前需要删除的key不在叶子节点上，则找出后继key，用后继key的值替换需要删除的key，然后删除后继key所在的叶子节点上删除后继key。
- 可以得出，在234树上删除节点，最终一定是在叶子节点上删除key。
- 如果最终删除的key所在叶子节点是3,4节点，直接删除即可。
- 如果最终删除的key所在的叶子节点是2节点：
- 如果左右兄弟节点有的借（左右兄弟节点不是二节点），则父节点中的key下移到该的节点，兄弟节点中的key上移到父节点。
- 如果左右兄弟节点没得借，且父亲节点有的借（左右兄弟节点是二节点，父亲节点不是二节点），该节点在父亲节点中的直接父key下移与兄弟节点合并（直接父key下移与兄弟节点中的key合并，可以理解为：因为父亲节点少了一个分支，所有父亲节点需要降阶成低一级的节点）。
举例：删除16
- 如果左右兄弟节点没得借，父亲节点也没得借（兄弟节点和父亲节点都是二节点），父亲节点和兄弟节点合并形成一个三节点，把合并后的3节点当成当前节点，按照下面的几种情况操作；总体来说就是因为父亲和兄弟合并导致减少了一层，那么必须整体上减少一层，或者中间某层把当前的分支合并或者增加一层。
- 场景1：如果兄弟节点有的借，不管父亲节点是什么；当前节点的父亲节点中的直接父key左旋或者右旋，当前节点的父亲节点中的父key变成其右（左）孩子的左（右）节点，删除结束。
举例：合并后的当前节点是二节点，删除7，当前节点变成9,11。
举例，合并后当前节点的父节点不是二节点
- 场景2：兄弟节点没得借（是二节点），当前节点的父节点也是二节点没得借，当前节点的父节点和兄弟节点合并，把合并后的节点作为当前节点重复场景1、场景2和场景3，直到234树平衡。
举例，删除7
- 场景3：当前节点的兄弟节点是二节点没得借，父节点是3,4节点有的借，父节点中的直接父key下移到兄弟节点与兄弟节点合并（父节点中的key下移是为了解决少一层的问题 ），删除结束。
参考
- http://www.cnblogs.com/nullzx/
- https://blog.csdn.net/qq_25940921/article/details/82183601?utm_medium=distribute.pc_relevant_t0.none-task-blog-OPENSEARCH-1.control&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-OPENSEARCH-1.control
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/100392.html
