久久久精品2019中文字幕神马_欧美亚洲一区三区_欧美大人香蕉在线_精品88久久久久88久久久_中文字幕一区二区三区在线播放 _精品国产一区二区三区久久影院_欧洲av在线精品_粉嫩av一区二区三区_亚洲欧美一区二区三区极速播放_国产亚洲精品久久

(資料圖片)

B+樹相關(guān)介紹

B+樹是一棵多叉排序樹，即每個非葉子節(jié)點可以包含多個子節(jié)點，其整體結(jié)構(gòu)呈扁平化，所以其非常適配于數(shù)據(jù)庫和操作系統(tǒng)的文件系統(tǒng)中。且B+樹能夠保持數(shù)據(jù)的穩(wěn)定有序，插入和刪除都擁有較穩(wěn)定的對數(shù)時間復(fù)雜度。

B+樹的特性：以 m 階為例，m 表示內(nèi)部節(jié)點即非葉子節(jié)點可以包含的最大子節(jié)點個數(shù) maximumNum

• 若一個內(nèi)部節(jié)點有 \(n(n <= m)\) 個子節(jié)點，則該內(nèi)部節(jié)點應(yīng)包含 \(n - 1\) 個關(guān)鍵字，也就是索引值
• 除根節(jié)點和葉子節(jié)點外，其他節(jié)點至少包含 Math.ceil(m / 2)個子節(jié)點，這是因為B+樹的生成順序?qū)е碌?ul>
• 最開始，B+樹只有一個根節(jié)點和若干不超過m個的葉子節(jié)點；
• 逐漸添加，導(dǎo)致葉子節(jié)點超過m時，此時根節(jié)點的子節(jié)點個數(shù)大于m，不符合要求，需要分裂
• 分裂則導(dǎo)致增加2個內(nèi)部節(jié)點，其中一個內(nèi)部節(jié)點個數(shù)為(m+1)/2，另一個為(m+2)/2
• 其他內(nèi)部節(jié)點也是如此規(guī)律形成，所以所有內(nèi)部節(jié)點的子節(jié)點個數(shù)均大于Math.ceil(m / 2)

B+樹實現(xiàn)

目前實現(xiàn)的B+樹的簡易版，葉子節(jié)點是存儲的Entry鍵值對，內(nèi)部節(jié)點存儲的是Integer索引，后續(xù)有時間再進行泛型的通用擴展。

節(jié)點定義

抽象公共父類 Node

package bplustree;public abstract class Node {    InternalNode parent;    // 父節(jié)點    public Node() {}        public abstract boolean isValid();          // 判斷刪除節(jié)點后各B+樹節(jié)點是否滿足要求    public abstract boolean isAvailable();      // 判斷B+樹節(jié)點是否可以分裂節(jié)點給其他節(jié)點    public abstract boolean isMergeable();      // 判斷B+樹節(jié)點是否可以和其他節(jié)點合并}

內(nèi)部節(jié)點定義

public class InternalNode extends Node{    int maxChildNodes;                   // 子節(jié)點個數(shù)最大值 m，m為階數(shù)    int minChildNodes;                   // 除根節(jié)點及葉子節(jié)點外，子節(jié)點個數(shù)最小值 ceil(m / 2)        int curNodesNum;                     // 內(nèi)部節(jié)點當前的子節(jié)點個數(shù)    InternalNode leftSibling;            // 左兄弟節(jié)點    InternalNode rightSibling;           // 右兄弟節(jié)點    Integer[] keys;                      // 內(nèi)部節(jié)點當前的索引值，最多有 m - 1 個    Node[] childPointers;                // 內(nèi)部節(jié)點當前的子節(jié)點，最多有 m 個}

葉子節(jié)點定義

public class LeafNode extends Node {    int maximumNum;                      // 葉子節(jié)點最多元素個數(shù) m - 1    int minimumNum;                          int curNum;                          // 葉子節(jié)點當前的元素個數(shù)    LeafNode leftSibling;                // 左兄弟和右兄弟形成雙向鏈表             LeafNode rightSibling;    Entry[] entries;                     // 葉子節(jié)點鍵值對，不僅存儲索引值，也存儲其他值信息}class Entry implements Comparable {    Integer key;    String value;    public Entry(Integer key, String value) {        this.key = key;        this.value = value;    }    @Override    public int compareTo(Entry o) {        return key.compareTo(o.key);    }}

B+樹定義

public class BPlusTree {    int m;    InternalNode root;         // B+樹根節(jié)點    LeafNode head;             // 葉子節(jié)點的首元素}

查詢操作

單值查詢

B+樹的查找過程：根據(jù)查找的索引值k，從根節(jié)點向葉子節(jié)點搜索，對數(shù)時間復(fù)雜度。

public String search(int key) {    if (isEmpty()) {        return null;    }    // 樹查找    LeafNode leafNode = (this.root == null) ? this.head : findLeafNode(key);    Entry[] entries = leafNode.entries;        // 葉子節(jié)點內(nèi)進行二分查找    int index = binarySearch(entries, leafNode.curNum, key, null);    if (index == -1) {        return null;    }    else {        return entries[index]    }}// 從根節(jié)點開始查找private LeafNode findLeafNode(Integer key) {    return findLeafNode(root, key);}// 找到索引值所在的葉子節(jié)點private LeafNode findLeafNode(InternalNode internalNode, Integer key) {    Integer[] keys = internalNode.keys;    int i;    for (i = 0; i < internalNode.curNodesNum - 1; i++) {        if (key.compareTo(keys[i]) < 0) {            break;        }    }    Object child = internalNode.childPointers[i];    if (child instanceof LeafNode) {        return (LeafNode) child;    }    else {        return findLeafNode((InternalNode) child, key);    }}

區(qū)間查詢

B+樹區(qū)間查詢左值可能在的葉子節(jié)點位置，然后通過雙向鏈表向后遍歷。

// 閉區(qū)間 [left, right]public ArrayList searchRange(int left, int right) {    List values = new ArrayList<>();    LeafNode leafNode = findLeafNode(left);    // 查找左值可能存在的位置，并從該位置向后遍歷    boolean flag = true;    while (leafNode != null && flag) {        Entry[] entries = leafNode.entries;        for (Entry entry : entries) {            if (entry == null) {                break;            }                        if ( entry.key > right) {                flag = false;                break;            }            if (left <= entry.key && right >= entry.key) {                values.add(entry.value);            }        }        leafNode = leafNode.rightSibling;    }    return values;}

插入操作

B+樹的插入操作僅在葉子節(jié)點進行：

1. 若為空樹，則創(chuàng)建一個葉子節(jié)點，該葉子節(jié)點同時也是根節(jié)點，插入操作結(jié)束；
2. 根據(jù)插入的 key 值，找到應(yīng)該在的葉子節(jié)點插入；
   1. 若插入后葉子節(jié)點個數(shù)符合要求即小于m，則插入結(jié)束
   2. 若插入后葉子節(jié)點個數(shù)不符合要求即大于等于m，將該節(jié)點分裂成兩半，則判斷當前葉子節(jié)點是否為根節(jié)點
      1. 若當前葉子節(jié)點為根節(jié)點，則構(gòu)建一個新的root節(jié)點，指向分裂后的兩個子節(jié)點
      2. 若當前葉子節(jié)點不為根節(jié)點，則在父節(jié)點處添加一個新的子節(jié)點，新子節(jié)點則存儲原節(jié)點一半的值，并循環(huán)向上判斷中間節(jié)點是否滿足要求

public void insert(int key, String value) {    if (isEmpty()) {        this.head = new LeafNode(this.m, new Entry(key, value));    }    else {        LeafNode leafNode = (this.root == null) ? this.head : findLeafNode(key);        // 插入葉子節(jié)點失敗，即葉子節(jié)點中存儲已到達上限        if (!leafNode.insert(new Entry(key, value))) {            leafNode.entries[leafNode.curNum++] = new Entry(key, value);            sortEntries(leafNode.entries);            // 葉子節(jié)點分裂的位置            int mid = getIndexOfMidPointer();            Entry[] halfEntry = splitEntries(leafNode, mid);            // 若葉子節(jié)點為根節(jié)點，即parent為null            if (leafNode.parent == null) {                Integer[] parent_keys = new Integer[m];                    parent_keys[0] = halfEntry[0].key;                // 創(chuàng)建新的 root                InternalNode parent = new InternalNode(m, parent_keys);                leafNode.parent = parent;                parent.appendChildPointer(leafNode);            }            // 若葉子節(jié)點不為根節(jié)點            else {                int newParentKey = halfEntry[0].key;                leafNode.parent.keys[leafNode.parent.curNodesNum - 1] = newParentKey;                Arrays.sort(leafNode.parent.keys, 0, leafNode.parent.curNodesNum);            }            // 分裂后的另一半葉子節(jié)點，添加到父節(jié)點            LeafNode newLeafNode = new LeafNode(this.m, halfEntry, leafNode.parent);            // 分裂后的另一半葉子節(jié)點對應(yīng)的下標            int index = leafNode.parent.getIndexOfPointer(leafNode) + 1;            for (int i = index; i < leafNode.parent.childPointers.length - 1; i++) {                leafNode.parent.childPointers[i + 1] = leafNode.parent.childPointers[i];            }            leafNode.parent.childPointers[index] = newLeafNode;            // 關(guān)聯(lián)兄弟節(jié)點            newLeafNode.rightSibling = leafNode.rightSibling;            if (newLeafNode.rightSibling != null) {                newLeafNode.rightSibling.leftSibling = newLeafNode;            }            leafNode.rightSibling = newLeafNode;            newLeafNode.leftSibling = leafNode;            if (this.root == null) {                this.root = leafNode.parent;            }            else {                // 逐漸上浮，判斷插入是否會導(dǎo)致B+樹內(nèi)部節(jié)點不符合要求                InternalNode internalNode = leafNode.parent;                while (internalNode != null) {                    if (internalNode.isOverfull()) {                        splitInternalNode(internalNode);                    }                    else {                        break;                    }                    internalNode = internalNode.parent;                }            }        }    }}/** * 葉子節(jié)點插入，導(dǎo)致的上層內(nèi)部節(jié)點分裂 */private void splitInternalNode(InternalNode internalNode) {    InternalNode parent = internalNode.parent;    int mid = getIndexOfMidPointer();    Integer newParentKey = internalNode.keys[mid];    // 內(nèi)部節(jié)點的 node 分裂    Node[] halfPointers = splitChildPointers(internalNode, mid);    // 內(nèi)部節(jié)點的 key 分裂    Integer[] halfKeys = splitKeys(internalNode.keys, mid);    // 分裂后內(nèi)部節(jié)點的子節(jié)點個數(shù)    internalNode.curNodesNum = linearNullSearch(internalNode.childPointers);    InternalNode sibling = new InternalNode(this.m, halfKeys, halfPointers);    for (Node pointer : halfPointers) {        if (pointer != null) {            pointer.parent = sibling;        }    }    sibling.rightSibling = internalNode.rightSibling;    internalNode.rightSibling = sibling;    sibling.leftSibling = internalNode;    if (sibling.rightSibling != null) {        sibling.rightSibling.leftSibling = sibling;    }    // root node    if (parent == null) {        Integer[] keys = new Integer[this.m];        keys[0] = newParentKey;        InternalNode newRoot = new InternalNode(this.m, keys);        newRoot.appendChildPointer(internalNode);        newRoot.appendChildPointer(sibling);        this.root = newRoot;        internalNode.parent = newRoot;        sibling.parent = newRoot;    }    else {        parent.keys[parent.curNodesNum - 1] = newParentKey;        Arrays.sort(parent.keys, 0, parent.curNodesNum);        int index = parent.getIndexOfPointer(internalNode) + 1;        parent.insertChildPointer(sibling, index);        sibling.parent = parent;    }}private Node[] splitChildPointers(InternalNode node, int split) {    Node[] pointers = node.childPointers;    Node[] newPointers = new Node[this.m + 1];    for (int i = split + 1; i < pointers.length; i++) {        newPointers[i - split - 1] = pointers[i];        node.removePointer(i);    }    return newPointers;}private Integer[] splitKeys(Integer[] keys, int split) {    Integer[] newKeys = new Integer[m];    keys[split] = null;    for (int i = split + 1; i < keys.length; i++) {        newKeys[i - split] = keys[i];        keys[i] = null;    }    return newKeys;}

刪除操作

B+樹的刪除操作僅在葉子節(jié)點進行：

1. 若刪除后，葉子節(jié)點中的索引個數(shù)仍然滿足要求即大于等于Math.ceil(m / 2)時，將該葉子節(jié)點的其他索引左移一位，刪除結(jié)束；
2. 若刪除后，葉子節(jié)點中的索引個數(shù)不滿足最低要求，則查詢左右兄弟節(jié)點：
   1. 若左/右兄弟節(jié)點中索引個數(shù)大于Math.ceil(m / 2)，則從左/右兄弟節(jié)點中移動一個索引項到當前葉子節(jié)點中，并修改父節(jié)點的索引值，刪除結(jié)束
   2. 若左/右兄弟節(jié)點中索引個數(shù)等于Math.ceil(m / 2)，則將左/右節(jié)點與當前節(jié)點合并，修改父節(jié)點的索引記錄，并向上逐級判斷內(nèi)部節(jié)點是否因為頁合并導(dǎo)致索引項不滿足最低要求，刪除結(jié)束

public void delete(int key) {    if (isEmpty()) {        System.out.println("Invalid: The B+ tree is empty!");    }    else {        LeafNode leafNode = this.root == null ? this.head : findLeafNode(key);        int index = binarySearch(leafNode.entries, leafNode.curNum, key, null);        if (index < 0) {            System.out.println("Invalid: The key does not exist in the B+ tree!");        }        else {            leafNode.deleteAtIndex(index);            // 刪除后，葉子節(jié)點仍然滿足要求，刪除結(jié)束            if (leafNode.isValid()) {                LeafNode sibling;                InternalNode parent = leafNode.parent;                // 刪除后，葉子節(jié)點不滿足要求，左兄弟節(jié)點可以移動一個索引項到當前葉子節(jié)點                if (leafNode.leftSibling != null && leafNode.leftSibling.parent == parent && leafNode.leftSibling.isAvailable()) {                    sibling = leafNode.leftSibling;                    Entry entry = sibling.entries[sibling.curNum - 1];                    leafNode.insert(entry);                    sortEntries(leafNode.entries);                    sibling.deleteAtIndex(sibling.curNum - 1);                    // 更新 parent 的 key                    int pointIndex = getIndexOfLeafNode(parent.childPointers, leafNode);                    if (entry.key < parent.keys[pointIndex - 1]) {                        parent.keys[pointIndex - 1] = entry.key;                    }                }                // 刪除后，葉子節(jié)點不滿足要求，右兄弟節(jié)點可以移動一個索引項到當前葉子節(jié)點                else if (leafNode.rightSibling != null && leafNode.rightSibling.parent == parent && leafNode.rightSibling.isAvailable()) {                    sibling = leafNode.rightSibling;                    Entry entry = sibling.entries[0];                    leafNode.insert(entry);                    sortEntries(leafNode.entries);                    sibling.deleteAtIndex(0);                    // 更新 parent 的 key                    int pointIndex = getIndexOfLeafNode(parent.childPointers, leafNode);                    if (entry.key > parent.keys[pointIndex]) {                        parent.keys[pointIndex] = entry.key;                    }                }                // 刪除后，葉子節(jié)點不滿足要求，左兄弟節(jié)點可以與當前葉子節(jié)點合并                else if (leafNode.leftSibling != null && leafNode.leftSibling.parent == parent && leafNode.leftSibling.isMergeable()) {                    sibling = leafNode.leftSibling;                    int pointIndex = getIndexOfLeafNode(parent.childPointers, leafNode);                    parent.removeKey(pointIndex - 1);                    parent.removePointer(leafNode);                    sibling.rightSibling = leafNode.rightSibling;                    if (parent.isValid()) {                        handleDeficiency(parent);                    }                }                // 刪除后，葉子節(jié)點不滿足要求，右兄弟節(jié)點可以與當前葉子節(jié)點合并                else if (leafNode.rightSibling != null && leafNode.rightSibling.parent == parent && leafNode.rightSibling.isMergeable()) {                    sibling = leafNode.rightSibling;                    int pointIndex = getIndexOfLeafNode(parent.childPointers, leafNode);                    parent.removeKey(pointIndex);                    parent.removePointer(leafNode);                    sibling.leftSibling = leafNode.leftSibling;                    if (sibling.leftSibling == null) {                        this.head = sibling;                    }                    // 逐級向上層判斷是否滿足要求                    if (parent.isValid()) {                        handleDeficiency(parent);                    }                }                // 刪除后，B+樹為空                else if (this.root == null && this.head.curNum == 0) {                    this.head = null;                }            }        }    }}/** * 處理不滿足要求的內(nèi)部節(jié)點 * @param internalNode */private void handleInvalidInternalNode(InternalNode internalNode) {    InternalNode sibling;    InternalNode parent = internalNode.parent;    // 當前內(nèi)部節(jié)點為根節(jié)點    if (root == internalNode) {        for (int i = 0; i < internalNode.childPointers.length; i++) {            if (internalNode.childPointers[i] != null) {                if (internalNode.childPointers[i] instanceof InternalNode) {                    root = (InternalNode) internalNode.childPointers[i];                    root.parent = null;                }                else if (internalNode.childPointers[i] instanceof LeafNode) {                    root = null;                }            }        }    }    // 左兄弟節(jié)點可以移動索引項    else if (internalNode.leftSibling != null && internalNode.leftSibling.isAvailable()) {        sibling = internalNode.leftSibling;        Integer key = sibling.keys[internalNode.curNodesNum - 2];        Node pointer = sibling.childPointers[internalNode.curNodesNum - 1];        shiftKeys(internalNode.keys, 1);        shiftPointers(internalNode.childPointers, 1);        internalNode.keys[0] = key;        internalNode.childPointers[0] = pointer;        sibling.removePointer(pointer);    }    // 右兄弟節(jié)點可以移動索引項    else if (internalNode.rightSibling != null && internalNode.rightSibling.isAvailable()) {        sibling = internalNode.rightSibling;        Integer key = sibling.keys[0];        Node pointer = sibling.childPointers[0];        internalNode.keys[internalNode.curNodesNum - 1] = parent.keys[0];        internalNode.childPointers[internalNode.curNodesNum] = pointer;        parent.keys[0] = key;        sibling.removePointer(0);        shiftPointers(sibling.childPointers, -1);    }    // 左兄弟節(jié)點可以合并    else if (internalNode.leftSibling != null && internalNode.leftSibling.isMergeable()) {        sibling = internalNode.leftSibling;        int index = -1;        for (int i = 0; i < parent.childPointers.length; i++) {            if (parent.childPointers[i] == internalNode) {                index = i;                break;            }        }        parent.keys[index - 1] = parent.keys[index];        for (int i = index; i < parent.keys.length - 1; i++) {            parent.keys[i] = parent.keys[i + 1];        }        shiftPointers(internalNode.childPointers, (int) Math.ceil(m / 2.0));        for (int i = 0; i < (int) Math.ceil(m / 2.0); i++) {            internalNode.childPointers[i] = sibling.childPointers[i];        }        internalNode.leftSibling = sibling.leftSibling;        if (internalNode.leftSibling != null) {            internalNode.leftSibling.rightSibling = internalNode;        }        if (parent != null && parent.isValid()) {            handleInvalidInternalNode(parent);        }    }    // 右兄弟節(jié)點可以合并    else if (internalNode.rightSibling != null && internalNode.rightSibling.isMergeable()) {        sibling = internalNode.rightSibling;        int index = -1;        for (int i = 0; i < parent.childPointers.length; i++) {            if (internalNode == parent.childPointers[i]) {                index = i;                break;            }        }        parent.keys[index] = parent.keys[index + 1];        for (int i = index + 2; i < parent.keys.length; i++) {            parent.keys[i - 1] = parent.keys[i];        }        for (int i = 0; i < (int) Math.ceil(m / 2.0); i++) {            internalNode.childPointers[internalNode.curNodesNum++] = sibling.childPointers[i];        }        internalNode.rightSibling = sibling.rightSibling;        if (internalNode.rightSibling != null) {            internalNode.rightSibling.leftSibling = internalNode;        }        if (parent != null && parent.isValid()) {            handleInvalidInternalNode(parent);        }    }}

參考文章：

1. B+樹