b樹

定義

一顆b樹T是具有一下性質(zhì)的有根樹

  1. 每個節(jié)點x均有如下屬性：
  • n表示存儲在該節(jié)點的關(guān)鍵字個數(shù)
  • n個關(guān)鍵字本身key1、key2……keyn以非降序存放，即key1 <= key2 <= …… <= keyn
  • 一個leaf布爾值表示該節(jié)點是否為葉節(jié)點
  1. 每個內(nèi)部節(jié)點包含了n+1個孩子糟红，葉節(jié)點沒有孩子
  2. 關(guān)鍵字keyi對存儲在各子樹中的關(guān)鍵字范圍加以分割：即比keyi小的元素在其左子樹，比keyi大的元素在其右子樹
  3. 每個葉節(jié)點具有相同的深度
  4. 每個節(jié)點包含的關(guān)鍵字個數(shù)有上界與下界。我們定義B樹的最小度數(shù)為t合武，則除根節(jié)點外的每個節(jié)點至少有t-1個關(guān)鍵字前硫，每個節(jié)點最多有2t-1個關(guān)鍵字胞得。
Paste_Image.png

作用

B樹是為磁盤或其他直接存取的輔助存儲設(shè)備而設(shè)計的一種平衡搜索樹。
主存對磁盤的讀取是以頁面為單位的屹电，一個頁面是連續(xù)的存儲單元組成阶剑，一旦從主存讀取不到，就會從磁盤替換頁面危号，同時一次磁盤I/O耗時很多牧愁。因為節(jié)點大，高度小的樹進(jìn)行的磁盤I/0次數(shù)就少外莲，所以總磁盤I/O耗時少猪半。

實現(xiàn)

用java實現(xiàn)了B樹的增刪改查
實現(xiàn)代碼:

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

private final int t;  //度數(shù)

private Node<E, F> T = null;  //根節(jié)點

private int height = 0;    //數(shù)的高度

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) { //可改進(jìn)為折半查找
            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) { //可改進(jìn)為折半查找
            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) { //可改進(jìn)為折半查找
            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) { //說明分裂的是根節(jié)點
        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) { //可改進(jìn)為折半查找
            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;
    }
}

//調(diào)用時 p.n>t-1 || p == T
private F nodeDelete(Node<E, F> p, int i) {
    if (p.isLeaf) {
        //只有在T為葉子節(jié)點的時候T才可能為空
        F value = p.delete(i).value;
        whenRootshouldBeNull();
        return value;
    } else { 
        //將兩個孩子節(jié)點與要刪除的值合并,再刪除那個合并點中的那個值
        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) {  //如果是根節(jié)點且根節(jié)點沒key了,就換根節(jié)點
                T = newNode;
                height--;
            }
            
            //再遞歸處理這個加入的節(jié)點 刪掉mid
            //這個加入的節(jié)點n==2t-1,符合條件
            return nodeDelete(newNode, newNode.getValueIndex(mid));
        } else {
            //把孩子節(jié)點的值換過來,再對孩子節(jié)點刪掉該值
            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);
        }
    }
}

//當(dāng)p節(jié)點.n為t-1時調(diào)用此程序
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);//假設(shè)父節(jié)點n>t-1
    if (father.c[nearj].n > t-1) {//從相鄰結(jié)點借一個關(guān)鍵字過來
        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 {
        //把這個結(jié)點與其相鄰結(jié)點合并，合并時需要把父結(jié)點的一個關(guān)鍵字加進(jìn)來
        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);
        }   
        
        //父節(jié)點為空了
        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) {  //沒有考慮非葉子節(jié)點的問題
    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) { //可改進(jìn)為折半查找
            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樹中插入一個關(guān)鍵字,只用考慮節(jié)點的關(guān)鍵字?jǐn)?shù)目是否為2*t-1偷线。

  • 關(guān)鍵字?jǐn)?shù)目不為2*t-1
    直接插入關(guān)鍵字就可以磨确。
  • 關(guān)鍵字?jǐn)?shù)目為2t-1
    需要分裂節(jié)點，將節(jié)點的中間關(guān)鍵字提上去給父節(jié)點声邦，其他的關(guān)鍵字分成兩個節(jié)點乏奥，各為t-1個關(guān)鍵字。再插入關(guān)鍵字翔忽。但是這時就需要考慮父節(jié)點關(guān)鍵字?jǐn)?shù)目是否為2    t-1英融。所以在遍歷b樹的時候發(fā)現(xiàn)節(jié)點關(guān)鍵字?jǐn)?shù)目為2*t-1的時候就要對它進(jìn)行分裂，再向下遍歷歇式。

刪除操作比插入操作考慮的情況更多驶悟，更復(fù)雜，可以參考
http://blog.csdn.net/swordmanwk/article/details/6549480

更詳細(xì)內(nèi)容可以參考《算法導(dǎo)論》

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末材失，一起剝皮案震驚了整個濱河市痕鳍，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌龙巨，老刑警劉巖笼呆，帶你破解...
    沈念sama閱讀 222,590評論 6贊 517
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異旨别，居然都是意外死亡诗赌，警方通過查閱死者的電腦和手機，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,157評論 3贊 399
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門秸弛，熙熙樓的掌柜王于貴愁眉苦臉地迎上來铭若，“玉大人洪碳，你說我怎么就攤上這事〉鹜溃” “怎么了瞳腌？”我有些...
    開封第一講書人閱讀 169,301評論 0贊 362
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵，是天一觀的道長镜雨。 經(jīng)常有香客問我嫂侍，道長，這世上最難降的妖魔是什么荚坞？ 我笑而不...
    開封第一講書人閱讀 60,078評論 1贊 300
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任挑宠，我火速辦了婚禮，結(jié)果婚禮上西剥，老公的妹妹穿的比我還像新娘痹栖。我一直安慰自己，他們只是感情好瞭空，可當(dāng)我...
    茶點故事閱讀 69,082評論 6贊 398
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布。 她就那樣靜靜地躺著疗我，像睡著了一般咆畏。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上吴裤，一...
    開封第一講書人閱讀 52,682評論 1贊 312
  • 城市分裂傳說
    那天旧找，我揣著相機與錄音，去河邊找鬼麦牺。 笑死钮蛛，一個胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的剖膳。 我是一名探鬼主播魏颓，決...
    沈念sama閱讀 41,155評論 3贊 422
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼吱晒！你這毒婦竟也來了甸饱？” 一聲冷哼從身側(cè)響起，我...
    開封第一講書人閱讀 40,098評論 0贊 277
  • 萬榮殺人案實錄
    序言：老撾萬榮一對情侶失蹤仑濒，失蹤者是張志新（化名）和其女友劉穎叹话，沒想到半個月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體墩瞳，經(jīng)...
    沈念sama閱讀 46,638評論 1贊 319
  • ?護林員之死
    正文 獨居荒郊野嶺守林人離奇死亡驼壶，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,701評論 3贊 342
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年，在試婚紗的時候發(fā)現(xiàn)自己被綠了喉酌。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片热凹。...
    茶點故事閱讀 40,852評論 1贊 353
  • 活死人
    序言：一個原本活蹦亂跳的男人離奇死亡箩溃，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出碌嘀，到底是詐尸還是另有隱情涣旨，我是刑警寧澤，帶...
    沈念sama閱讀 36,520評論 5贊 351
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布股冗，位于F島的核電站霹陡，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏止状。R本人自食惡果不足惜烹棉，卻給世界環(huán)境...
    茶點故事閱讀 42,181評論 3贊 335
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望怯疤。 院中可真熱鬧浆洗，春花似錦、人聲如沸集峦。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,674評論 0贊 25
  • 一樁弒父案，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽塔淤。三九已至摘昌，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間高蜂，已是汗流浹背聪黎。 一陣腳步聲響...
    開封第一講書人閱讀 33,788評論 1贊 274
  • 情欲美人皮
    我被黑心中介騙來泰國打工， 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留备恤，地道東北人稿饰。 一個月前我還...
    沈念sama閱讀 49,279評論 3贊 379
  • 代替公主和親
    正文 我出身青樓，卻偏偏與公主長得像露泊，于是被迫代替她去往敵國和親喉镰。 傳聞我的和親對象是個殘疾皇子，可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,851評論 2贊 361

推薦閱讀更多精彩內(nèi)容

  • B樹的定義 一棵m階的B樹滿足下列條件： 樹中每個結(jié)點至多有m個孩子滤淳。 除根結(jié)點和葉子結(jié)點外梧喷，其它每個結(jié)點至少有m...
    文檔隨手記閱讀 13,241評論 0贊 25
  • 原文鏈接 B樹 1.前言： 動態(tài)查找樹主要有：二叉查找樹（Binary Search Tree），平衡二叉查找樹（...
    非典型程序員閱讀 1,164評論 0贊 3
  • B樹 1.前言： 動態(tài)查找樹主要有：二叉查找樹（Binary Search Tree）脖咐，平衡二叉查找樹（Balan...
    鐵甲依然在_978f閱讀 1,447評論 0贊 4
  • 1 概述 前一講提到了二叉搜索樹铺敌，從直覺的角度看，貌似較好地解決了快速搜索的問題屁擅，其實不然偿凭。如果給定一個關(guān)鍵字序列...
    CodingTech閱讀 5,312評論 0贊 11
  • B-樹，就是B樹匾嘱，B樹的原英文名是B-tree,所以很多翻譯為B-樹,就會很多人誤以為B-樹是一種樹斤斧、B樹是另外一...
    xx1994閱讀 23,814評論 1贊 17