Re: Re: 求教，存在2阶的B-树么

2017/6/28镜像同步4 回复

你说的B-树是B-tree么? B树插入操作是自底向上的首先，找到应该插入的叶节点，如果叶节点(Node1)的关键字数量已满(关键字数量 N=2*t-1)，那么对该叶节点进行一次分裂操作。该分裂操作会将一个关键字插入到其父节点Node2中，如果Node2关键字数量也满了，那么会继续分裂并将一个关键字插入到Node2的父节点(Node3)中，......(递归向上，直至遇到关键字数量非满的节点) 这种方式会需要节点含有父节点的指针，否则定位父节点会比较耗时，但是含有父节点的指针又会导致空间浪费。于是可以换一种方式，自顶向下插入节点(可以看看算法导论伪代码)：从根节点沿着查询路径直至叶节点，如果发现某个节点的关键字数量已满，则预先进行一次分裂操作，这种方式的好处是：当某个节点需要分裂，那么其父节点一定是关键字非满的节点。于是，在到达叶节点时，就可以将关键字插入叶节点了额，至于你说的2阶，应该就是对应t=2的情况，感觉过程是一样的啊

订阅后，新回复会通过你的通知中心匿名送达。

4 条回复

whyware机器人#1 · 2017/6/28

恩，是B减树。我的想法是，当插入节点时，如果分裂，按照书上的定义，添加到根结点的是第一个关键字，比如根是20，左孩子是15，要插入一个10，那么，10这个关键字会跑到20那里，这样就出现了错误，也会产生没有关键字的空节点。我在想会不会是书上的定义在二阶的时候不同或者是二阶的B减数根本没有意义【在 liuyehcf 的大作中提到: 】 : 你说的B-树是B-tree么? : : B树插入操作是自底向上的 : 首先，找到应该插入的叶节点，如果叶节点(Node1)的关键字数量已满(关键字数量 N=2*t-1)，那么对该叶节点进行一次分裂操 : ......... 发自「贵邮」

liuyehcf机器人#2 · 2017/6/29

先明确一下，假设阶数/度是t，那么除了根节点之外的其他节点至少有t-1个关键字，最多有2t-1个关键字。再来看你说的二阶，我的理解对应的就是t=2，那么除了根节点之外的节点至少有t-1=1个关键字，最多有2t-1=3个关键字。根据你描述的例子：首先插入20，此时有且仅有一个根节点，且只有一个关键字20。然后插入15，此时有且仅有一个根节点，含有关键字15，20。继续插入10，此时仍然有且仅有一个根节点，含有关键字10，15，20。可能我理解错你的意思了，你可以画个图描述一下，文字不太直观【在 whyware 的大作中提到: 】 : 恩，是B减树。我的想法是，当插入节点时，如果分裂，按照书上的定义，添加到根结点的是第一个关键字，比如根是20，左孩子是15，要插入一个10，那么，10这个关键字会跑到20那里，这样就出现了错误，也会产 : ......... 发自「贵邮」

littleneko机器人#3 · 2017/6/29

没有B-树，没有B-树，没有B-树，重要的事情说三遍。只有B树（B-Tree）和B+树（B+Tree）

whyware机器人#4 · 2017/6/29

恩，看错了，由于是自学，看错了…… 【在 littleneko 的大作中提到: 】 : 没有B-树，没有B-树，没有B-树，重要的事情说三遍。只有B树（B-Tree）和B+树（B+Tree） : 发自「贵邮」