b树

定义

一颗b树T是具有一下性质的有根树

每个节点x均有如下属性：

n表示存储在该节点的关键字个数
n个关键字本身key1、key2……keyn以非降序存放，即key1 <= key2 <= …… <= keyn
一个leaf布尔值表示该节点是否为叶节点

每个内部节点包含了n+1个孩子，叶节点没有孩子
关键字keyi对存储在各子树中的关键字范围加以分割：即比keyi小的元素在其左子树，比keyi大的元素在其右子树
每个叶节点具有相同的深度
每个节点包含的关键字个数有上界与下界。我们定义B树的最小度数为t，则除根节点外的每个节点至少有t-1个关键字，每个节点最多有2t-1个关键字。

Paste_Image.png

作用

B树是为磁盘或其他直接存取的辅助存储设备而设计的一种平衡搜索树。
主存对磁盘的读取是以页面为单位的，一个页面是连续的存储单元组成，一旦从主存读取不到，就会从磁盘替换页面，同时一次磁盘I/O耗时很多。因为节点大，高度小的树进行的磁盘I/0次数就少，所以总磁盘I/O耗时少。

实现

用java实现了B树的增删改查
实现代码:

public class BTree<E extends Comparable<E>, F> {

private final int t;  //度数

private Node<E, F> T = null;  //根节点

private int height = 0;    //数的高度

public int getHeight() {
    return height;
}

public BTree(int t) {
    this.t= t;
}

@Override
public String toString() {
    if (T == null) {
        return null;
    }
    return T.toString();
}

public F search(E e) {
    if (T == null) {
        return null;
    }
    
    int i = 0;
    Node<E, F> p = T;

    while (true) {
        while (i < p.n && e.compareTo(p.getKey(i)) > 0) { //可改进为折半查找
            i++;
        }
        
        if (i != p.n && p.getKey(i).compareTo(e) == 0) {
            return p.getValue(i);
        }
        
        if (p.isLeaf) {
            return null;
        }
        
        p = p.c[i];
        i = 0;
    }
    
    
}

public void update(E e, F f) {
    if (T == null) {
        return;
    }
    
    int i = 0;
    Node<E, F> p = T;

    while (true) {
        while (i < p.n && e.compareTo(p.getKey(i)) > 0) { //可改进为折半查找
            i++;
        }
        
        if (i != p.n && p.getKey(i).compareTo(e) == 0) {
            p.kavs[i].value = f;
            return;
        }
        
        if (p.isLeaf) {
            return;
        }
        
        p = p.c[i];
        i = 0;
    }
}

private void insertWhenRootIsNulll(E e, F f) {
    T = new Node<E, F>(true);
    T.add(e, f);
    T.tier=0;
    height = 1;
}

public void insert(E e, F f) {
    if (T == null) {
        insertWhenRootIsNulll(e, f);
        return;
    } 
    
    Node<E, F> father = null;
    Node<E, F> node = T;
    int i = 0;
    while (true) {
        if (node.n == 2*t-1) {
            node=nodeSplit(father, node, e);
        }
        
        if (node.isLeaf) {
            node.add(e, f);
            return;
        }
        
        while (i < node.n && e.compareTo(node.getKey(i)) > 0) { //可改进为折半查找
            i++;
        }
        
        father = node;
        node = node.c[i];
        i = 0;
    }
}

private Node<E, F> nodeSplit(Node<E, F> father, Node<E, F> node, E e) {
    int mid = t-1;
    //System.out.println("mid = " + mid);
    Node<E, F> left = new Node<E, F>(node.isLeaf);
    left.copyKeyAndValues(node, 0, mid-1);
    left.tier = node.tier;
    //System.out.println("left" + 0 + " " + (mid-1));
    Node<E, F> right = new Node<E, F>(node.isLeaf);
    right.copyKeyAndValues(node, mid+1, node.n-1);
    right.tier = node.tier;
    //System.out.println("right" + (mid+1) + " " + (node.n-1));
    
    if (father == null) { //说明分裂的是根节点
        father = new Node<E, F>(false);
        father.tier = node.tier+1;
        height++;
        T = father;
    }
    
    father.deleteChild(node);
    int index = father.add(node.kavs[mid]);
    father.addChild(left, index);
    father.addChild(right, index+1);
    left.copyChildren(node, 0, mid);
    right.copyChildren(node, mid+1, node.n);
    
    return e.compareTo(node.kavs[mid].key) > 0? right:left;
}


public F delete(E e) {  //问题很多,还需要修改
    if (T == null) {
        return null;
    }
    
    return seekAndDeleteNode(e, null, T, -1);
}

private F seekAndDeleteNode(E key, Node<E, F> father, Node<E, F> p, int j) {
    int i = 0;
    while (true) {
        if (p.n == t-1) {
            p = nodeDeleteHandle(father, p, j);
        }
        
        while (i < p.n && key.compareTo(p.getKey(i)) > 0) { //可改进为折半查找
            i++;
        }
        
        if (i != p.n && p.getKey(i).compareTo(key) == 0) {
            break;
        }
        
        if (p.isLeaf) {
            return null;
        }
        
        father = p;
        p = p.c[i];
        j=i;
        i = 0;
    }
    
    return nodeDelete(p, i);
}

private void whenRootshouldBeNull() {
    if (T.n == 0) {
        T = null;
        height = 0;
    }
}

//调用时 p.n>t-1 || p == T
private F nodeDelete(Node<E, F> p, int i) {
    if (p.isLeaf) {
        //只有在T为叶子节点的时候T才可能为空
        F value = p.delete(i).value;
        whenRootshouldBeNull();
        return value;
    } else { 
        //将两个孩子节点与要删除的值合并,再删除那个合并点中的那个值
        if (p.c[i].n == t-1 && p.c[i+1].n == t-1) {  
            Node<E, F> leftchild = p.deleteChild(i);
            Node<E, F> rightchild = p.deleteChild(i);
            KeyAndValue<E, F> mid = p.delete(i);
            Node<E, F> newNode = nodeUnion(leftchild, rightchild, mid);
            p.addChild(newNode, i);
            
            if (p.n == 0 && p == T) {  //如果是根节点且根节点没key了,就换根节点
                T = newNode;
                height--;
            }
            
            //再递归处理这个加入的节点 删掉mid
            //这个加入的节点n==2t-1,符合条件
            return nodeDelete(newNode, newNode.getValueIndex(mid));
        } else {
            //把孩子节点的值换过来,再对孩子节点删掉该值
            int neari = p.c[i].n > p.c[i+1].n? i : i+1;
            Node<E, F> other = p.c[neari];
            p.kavs[i] = neari == i ? other.kavs[other.n-1] : other.kavs[0];
            
            //再递归处理other 删掉 p.kavs[i]
            //因为other.n>t-1不一定成立
            return seekAndDeleteNode(p.kavs[i].key, p, p.c[neari], neari);
        }
    }
}

//当p节点.n为t-1时调用此程序
private Node<E, F> nodeDeleteHandle(Node<E, F> father, Node<E, F> p, int j) {  
    if (p == T) {
        return p;
    }
    
    int nearj = (j == father.n ? j-1:j+1);//假设父节点n>t-1
    if (father.c[nearj].n > t-1) {//从相邻结点借一个关键字过来
        KeyAndValue<E, F> kav1 = null;
        KeyAndValue<E, F> kav2 = null;
        Node<E, F> child = null;
        if (nearj == j+1) {
            if (!p.isLeaf) {
                child = father.c[nearj].deleteChild(0);
            }
            
            kav2 = father.kavs[j];
            kav1 = father.c[nearj].delete(0);
            p.kavs[p.n] = kav2;
            p.n++;
            father.kavs[j] = kav1;
            if (!p.isLeaf) {
                p.addChild(child, p.n);
            }
        } else { //nearj==j-1
            if (!p.isLeaf) {
                child = father.c[nearj].deleteChild(father.c[nearj].n);
            }
            kav1 = father.c[nearj].delete(father.c[nearj].n-1);
            kav2 = father.kavs[j-1];
            p.add(kav2);
            father.kavs[j-1] = kav1;
            if (!p.isLeaf) {
                p.addChild(child, 0);
            }
        }
        
        return p;
        
    } else {
        //把这个结点与其相邻结点合并，合并时需要把父结点的一个关键字加进来
        Node<E, F> other = father.c[nearj];
        Node<E, F> newNode = null;
        father.deleteChild(p);
        father.deleteChild(other);
        if (nearj == j+1) {
            KeyAndValue<E, F> mid = father.delete(j);
            newNode = nodeUnion(p, other, mid);
            father.addChild(newNode, j);
        } else { //nearj==j-1
            KeyAndValue<E, F> mid = father.delete(j-1);
            newNode = nodeUnion(other, p, mid);
            father.addChild(newNode, j-1);
        }   
        
        //父节点为空了
        if (father.n == 0 && father == T) {
            T = newNode;
            height--;
        }
        
        return newNode;
    }
    
}


private Node<E, F> nodeUnion(Node<E, F> node1, 
        Node<E, F> node2, KeyAndValue<E, F> mid) {  //没有考虑非叶子节点的问题
    node1.kavs[node1.n] = mid;
    node1.n++;
    for (int i = 0; i < node2.n; i++) {
        node1.kavs[i+node1.n] = node2.kavs[i];
        if (!node1.isLeaf) {
            node1.c[i+node1.n] = node2.c[i];
        }
    }
    node1.n += node2.n;
    if (!node1.isLeaf) {
        node1.c[node1.n] = node2.c[node2.n];
    }
    
    return node1;
}



class Node<E extends Comparable<E>, F>{
    int n = 0;
    int tier = 0;
    KeyAndValue<E, F>[] kavs = new KeyAndValue[2*t-1];
    boolean isLeaf;
    Node<E, F>[] c = null;
    
    @Override
    public String toString() {
        StringBuffer s = new StringBuffer();
        s.append(this.tier + " ");
        for (int i = 0; i < n; i++) {
            s.append(kavs[i] + " ");
        }
        s.append("\n");
        if (!isLeaf) {
            for (int j = 0; j <= n; j++) {
                s.append(c[j]);
            }
        }
        return s.toString();
    }

    Node (boolean isLeaf) {
        if(!isLeaf) {
            c = new Node[2*t];
        }
        this.isLeaf = isLeaf;
    }
    
    E getKey(int i) {
        return kavs[i].key;
    }
    
    F getValue(int i) {
        return kavs[i].value;
    }
    
    //使用前提:存在kav
    int getValueIndex(KeyAndValue<E, F> kav) {
        int i = 0;
        while (i < n && kav.key.compareTo(getKey(i)) > 0) { //可改进为折半查找
            i++;
        }
        return i;

    }
    
    void copyKeyAndValues(Node<E, F> n, int low, int high) {
        for (int i = low; i <= high; i++) {
            kavs[i-low] = n.kavs[i];
        }
        this.n=1+high-low;
    }
    
    void copyChildren(Node<E, F> n, int low, int high) {
        if (isLeaf) {
            return;
        }
        
        for (int i = low; i <= high; i++) {
            c[i-low] = n.c[i];
        }
    }
    
    void addChild(Node<E, F> node, int i) {
        if (isLeaf) {
            return;
        }

        int j = n;
        while(j > i) {
            c[j] = c[j-1];
            j--;
        }
        c[i] = node;
    }
    
    Node<E, F> deleteChild(int i) {
        if (isLeaf) {
            return null;
        }
        
        Node<E, F> child = c[i];
        for (int j = i; j < n; j++) {
            c[j] = c[j+1];
        }
        
        return child;
    }
    
    void deleteChild(Node<E, F> node) {
        if (isLeaf) {
            return;
        }
        
        boolean hasFind = false;
        for (int i = 0; i < n; i++) {
            if (c[i] == node) {
                hasFind = true;
            }
            
            if (hasFind) {
                c[i] = c[i+1];
            }
        }
    }
    
    KeyAndValue<E, F> delete(int i) {
        KeyAndValue<E, F> kav = kavs[i];
        for (int j = i; j < n-1; j++) {
            kavs[j] = kavs[j+1];
        }
        n--;
        
        return kav;
    }
    
    int add(E e, F f) {
        return add(new KeyAndValue<E, F>(e, f));
    }
    
    int add(KeyAndValue kav) {
        int i = n;
        //System.out.println("n = " + n);
        while (i != 0 && getKey(i-1).compareTo((E) kav.key) > 0) {
            kavs[i] = kavs[i-1];
            i--;
        }
        kavs[i] = kav; 
        
        n++;
        
        return i;
    }
    
    void changeToNonLeaf() {
        if (isLeaf) {
            isLeaf = false;
            c = new Node[2*t];
        }
    }
    
}

class KeyAndValue <E extends Comparable<E>, F> {
    E key = null;
    F value = null;
    
    @Override
    public String toString() {
        return "[" + key + "," + value + "]";
    }

    KeyAndValue(E key, F value) {
        this.key = key;
        this.value = value;
    } 
}
}

测试代码:

public static void main(String[] args) {
    BTree<Integer, String> t = new BTree<Integer, String>(3);
    int n = 16;

    for (int i = n-1; i >= 0; i--) {
        t.insert(i, i+"");
    }
    System.out.println(t);
    
    t.delete(n-1);
    System.out.println(t);
    
    t.update(1, "3");
    System.out.println(t);
}

插入

在B树中插入一个关键字,只用考虑节点的关键字数目是否为2*t-1。

关键字数目不为2*t-1
直接插入关键字就可以。
关键字数目为2t-1
需要分裂节点，将节点的中间关键字提上去给父节点，其他的关键字分成两个节点，各为t-1个关键字。再插入关键字。但是这时就需要考虑父节点关键字数目是否为2t-1。所以在遍历b树的时候发现节点关键字数目为2*t-1的时候就要对它进行分裂，再向下遍历。

删除操作比插入操作考虑的情况更多，更复杂，可以参考
http://blog.csdn.net/swordmanwk/article/details/6549480

更详细内容可以参考《算法导论》

最后编辑于：2017.12.10 23:09:16

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 211,817评论 6赞 492
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 90,329评论 3赞 385
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 157,354评论 0赞 348
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 56,498评论 1赞 284
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 65,600评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,829评论 1赞 290
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,979评论 3赞 408
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,722评论 0赞 266
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,189评论 1赞 303
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,519评论 2赞 327
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,654评论 1赞 340
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,329评论 4赞 330
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,940评论 3赞 313
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,762评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,993评论 1赞 266
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,382评论 2赞 360
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,543评论 2赞 349

b树

定义

作用

实现

插入

推荐阅读更多精彩内容