blocks|key|952652|text|B%2B树是一种自平衡搜索树.|type|unstyled|depth|inlineStyleRanges|entityRanges|data|952653|自平衡树需要保持最大树的深度与它所持有的元素数的对数成正比。|952654|B%2B就是这样做的，在插入和重新分配时进行拆分和添加层，在删除时删除节点。|952655|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

B+ tree is a self-balancing search tree.

Self-balancing trees need to maintain the maximum tree depth to be proportional to some logarithm of the number of elements it holds.

B+ does it this way, with splits and adding layers on insertion and redistribution and removing nodes on deletion.

blocks|key|952748|text|好吧我明白问题了。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|952749|B%2B树的性质|952750|所有的叶子都应该在相同的深度，每个叶节点中的最小元素应该等于树的深度。见下面的例子：|unordered-list-item|952751|所有的叶子都在相同的深度，这里d=+2。|952752|每个叶节点必须包含d个元素，否则必须执行重新分配和合并。|952753|所有数据指针都包含在叶节点中。|952754|所有元素都应包含在叶节点中。|952755|除了根以外，节点上的d到2*d键之间应该存在。|offset|length|style|CODE|952756|应该在d+%2B+1到2*d+%2B+1子指针之间存在。|952757|在下面给出的B%2B树中，每个节点都有2和2*2数据条目，除了根之外。每个节点都有一个最小的两个键。|952758|只有B%2B树的根只能少于d键，这是我们唯一的例外。|952759|在我的问题中，当您删除19时，B%2B树的属性没有被违反，但是当您删除20时，节点中包含的元素总数小于d，因此必须执行重新分配和合并，这样才不会违反B%2B树的属性。|952760|​|952761|📷|atomic|952762|952763|entityMap|0|IMAGE|mutability|IMMUTABLE|imageUrl|https://developer.qcloudimg.com/http-save/yehe-900000/de6a9d38452b75fa38c394a3d6b80160.png|imageAlt^0|0|0|0|0|0|0|0|A|1|C|3|0|3|5|9|7|0|H|1|J|3|0|0|B|2|X|2|0|0|0|1|0|0|0^^$0|@$1|2|3|4|5|6|7|1H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|1I|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|1J|8|@]|9|@]|A|$]]|$1|G|3|H|5|F|7|1K|8|@]|9|@]|A|$]]|$1|I|3|J|5|F|7|1L|8|@]|9|@]|A|$]]|$1|K|3|L|5|F|7|1M|8|@]|9|@]|A|$]]|$1|M|3|N|5|F|7|1N|8|@]|9|@]|A|$]]|$1|O|3|P|5|F|7|1O|8|@$Q|1P|R|1Q|S|T]|$Q|1R|R|1S|S|T]]|9|@]|A|$]]|$1|U|3|V|5|F|7|1T|8|@$Q|1U|R|1V|S|T]|$Q|1W|R|1X|S|T]]|9|@]|A|$]]|$1|W|3|X|5|6|7|1Y|8|@$Q|1Z|R|20|S|T]|$Q|21|R|22|S|T]]|9|@]|A|$]]|$1|Y|3|Z|5|6|7|23|8|@]|9|@]|A|$]]|$1|10|3|11|5|6|7|24|8|@$Q|25|R|26|S|T]|$Q|27|R|28|S|T]]|9|@]|A|$]]|$1|12|3|13|5|6|7|29|8|@]|9|@]|A|$]]|$1|14|3|15|5|16|7|2A|8|@]|9|@$Q|2B|R|2C|1|2D]]|A|$]]|$1|17|3|13|5|6|7|2E|8|@]|9|@]|A|$]]|$1|18|3|-4|5|6|7|2F|8|@]|9|@]|A|$]]]|19|$1A|$5|1B|1C|1D|A|$1E|1F|1G|-4]]]]

Okay I understood the issue.

Properties of B+ Tree. 

<ul>
<li>All leaves should be at the same depth, and the mininum element in each leaf node should be equal to depth of the tree. See the example below:</li>
<li>All the leaves are in same depth, and here d = 2.</li>
<li>Each leaf node must contain d number of elements, otherwise redistribution and merging has to be performed.</li>
<li>All the data pointers are contained in leaf nodes.</li>
<li>All elements should be contained in leaf nodes.</li>
<li>There should be between <code>d</code> to <code>2*d</code> keys at node except possibly the root.</li>
<li>There should be between <code>d + 1</code> to <code>2*d + 1</code> child pointers.</li>
</ul>

In the B+ Tree given below, each node has <code>2</code> and <code>2*2</code> data entries except possible the root. Each node has a mininum of 2 keys.

Only root of the B+ Tree can only fewer than d keys, its the only exception we have.

In my question, when you remove <code>19</code>, the property of B+ Tree is not violated but when you remove <code>20</code>, the total number of elements contained in the node is less than d. Hence redistribution and merging have to be performed so that the property of B+ tree is not violated.

<a href="https://i.stack.imgur.com/NqBU4.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/NqBU4.png" alt="enter image description here"></a>

My professor was giving a lecture on B+ Trees deletion, and I got very confused. According to him for deleting any key from a B+ Tree:

<pre><code>1- First navigate to the leaf *L* where it belongs.
2- If the *L* is at least half full if you can simply delete it.
3- If it contains d-1 elements then you need to redistribute and merge.
</code></pre>

If you see the below image, here I want to delete 19 and 20 from the B+ Tree.

<a href="https://i.stack.imgur.com/NBt66.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/NBt66.png" alt="enter image description here"></a>

After deleting 19 and 20 from the B+ Tree.

<a href="https://i.stack.imgur.com/eCgVD.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/eCgVD.png" alt="enter image description here"></a>

Question:

I am confused why the redistribution and merging is required here at all? If you just simply delete 19 and 20 from the leaf nodes without any distribution it should work right? Why redistribution is performed here? Could anyone explain? 

<blockquote>
 Is it because the left pointer of 24 is pointing to 20 but no 19.
 Thats why redistribution is required for 20 but not 19.
</blockquote>

Deleting key from a B+ Tree

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

EdgeOne AI 安全实战专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云AI代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

功能1上新10个字符

功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符功能2描述100个字符。

功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符功能2上新100个字符。

功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符功能5描述100个字符

功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符功能5上新100个字符

功能4上新

文章&问答评论现已支持表情

全新交互，全新视觉，新增快捷键、悬浮工具栏、高亮块等功能并同时优化现有功能，全面提升创作效率和体验

社区富文本编辑器全新改版！诚邀体验～ 

精选全网热门MCP server，让你的AI更好用 🚀

💥开发者 MCP广场重磅上线！

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

我的教授正在做一个关于B+树删除的讲座，我感到非常困惑。据他说，他删除了B+树中的任何密钥：1- First navigate to the leaf *L* where it belongs.2- If the *L* is at least half full if you can simply delete it.3- If it contains d-1 elements then you

问从B+树中删除密钥
EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问从B+树中删除密钥EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问从B+树中删除密钥
EN