欧美性啪啪_韩国av不卡_99国产精品免费观看视频re_日本在线中文_日韩毛片子_欧美福利在线观看_av美女在线播放_色偷偷偷_亚洲大片在线播放_曰韩在线_亚洲精品观看_国产午夜理论片不卡_三上悠亚一区二区三区在线_精品人伦一区二区三区四区蜜桃牛_国产精品久久久久久久久大全_日本人吃奶玩奶虐乳视频_99精品视频免费观看_日韩16p_欧日韩在线_av一区二区在线播放

(資料圖片)

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

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

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

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

B+樹(shù)實(shí)現(xiàn)

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

節(jié)點(diǎn)定義

抽象公共父類 Node

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

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

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

葉子節(jié)點(diǎn)定義

public class LeafNode extends Node {    int maximumNum;                      // 葉子節(jié)點(diǎn)最多元素個(gè)數(shù) m - 1    int minimumNum;                          int curNum;                          // 葉子節(jié)點(diǎn)當(dāng)前的元素個(gè)數(shù)    LeafNode leftSibling;                // 左兄弟和右兄弟形成雙向鏈表             LeafNode rightSibling;    Entry[] entries;                     // 葉子節(jié)點(diǎn)鍵值對(duì)，不僅存儲(chǔ)索引值，也存儲(chǔ)其他值信息}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+樹(shù)定義

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

查詢操作

單值查詢

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

public String search(int key) {    if (isEmpty()) {        return null;    }    // 樹(shù)查找    LeafNode leafNode = (this.root == null) ? this.head : findLeafNode(key);    Entry[] entries = leafNode.entries;        // 葉子節(jié)點(diǎn)內(nèi)進(jìn)行二分查找    int index = binarySearch(entries, leafNode.curNum, key, null);    if (index == -1) {        return null;    }    else {        return entries[index]    }}// 從根節(jié)點(diǎn)開(kāi)始查找private LeafNode findLeafNode(Integer key) {    return findLeafNode(root, key);}// 找到索引值所在的葉子節(jié)點(diǎn)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+樹(shù)區(qū)間查詢左值可能在的葉子節(jié)點(diǎn)位置，然后通過(guò)雙向鏈表向后遍歷。

// 閉區(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+樹(shù)的插入操作僅在葉子節(jié)點(diǎn)進(jìn)行：

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

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é)點(diǎn)失敗，即葉子節(jié)點(diǎn)中存儲(chǔ)已到達(dá)上限        if (!leafNode.insert(new Entry(key, value))) {            leafNode.entries[leafNode.curNum++] = new Entry(key, value);            sortEntries(leafNode.entries);            // 葉子節(jié)點(diǎn)分裂的位置            int mid = getIndexOfMidPointer();            Entry[] halfEntry = splitEntries(leafNode, mid);            // 若葉子節(jié)點(diǎn)為根節(jié)點(diǎn)，即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é)點(diǎn)不為根節(jié)點(diǎn)            else {                int newParentKey = halfEntry[0].key;                leafNode.parent.keys[leafNode.parent.curNodesNum - 1] = newParentKey;                Arrays.sort(leafNode.parent.keys, 0, leafNode.parent.curNodesNum);            }            // 分裂后的另一半葉子節(jié)點(diǎn)，添加到父節(jié)點(diǎn)            LeafNode newLeafNode = new LeafNode(this.m, halfEntry, leafNode.parent);            // 分裂后的另一半葉子節(jié)點(diǎn)對(duì)應(yīng)的下標(biāo)            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é)點(diǎn)            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 {                // 逐漸上浮，判斷插入是否會(huì)導(dǎo)致B+樹(shù)內(nèi)部節(jié)點(diǎn)不符合要求                InternalNode internalNode = leafNode.parent;                while (internalNode != null) {                    if (internalNode.isOverfull()) {                        splitInternalNode(internalNode);                    }                    else {                        break;                    }                    internalNode = internalNode.parent;                }            }        }    }}/** * 葉子節(jié)點(diǎn)插入，導(dǎo)致的上層內(nèi)部節(jié)點(diǎn)分裂 */private void splitInternalNode(InternalNode internalNode) {    InternalNode parent = internalNode.parent;    int mid = getIndexOfMidPointer();    Integer newParentKey = internalNode.keys[mid];    // 內(nèi)部節(jié)點(diǎn)的 node 分裂    Node[] halfPointers = splitChildPointers(internalNode, mid);    // 內(nèi)部節(jié)點(diǎn)的 key 分裂    Integer[] halfKeys = splitKeys(internalNode.keys, mid);    // 分裂后內(nèi)部節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(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+樹(shù)的刪除操作僅在葉子節(jié)點(diǎn)進(jìn)行：

1. 若刪除后，葉子節(jié)點(diǎn)中的索引個(gè)數(shù)仍然滿足要求即大于等于Math.ceil(m / 2)時(shí)，將該葉子節(jié)點(diǎn)的其他索引左移一位，刪除結(jié)束；
2. 若刪除后，葉子節(jié)點(diǎn)中的索引個(gè)數(shù)不滿足最低要求，則查詢左右兄弟節(jié)點(diǎn)：
   1. 若左/右兄弟節(jié)點(diǎn)中索引個(gè)數(shù)大于Math.ceil(m / 2)，則從左/右兄弟節(jié)點(diǎn)中移動(dòng)一個(gè)索引項(xiàng)到當(dāng)前葉子節(jié)點(diǎn)中，并修改父節(jié)點(diǎn)的索引值，刪除結(jié)束
   2. 若左/右兄弟節(jié)點(diǎn)中索引個(gè)數(shù)等于Math.ceil(m / 2)，則將左/右節(jié)點(diǎn)與當(dāng)前節(jié)點(diǎn)合并，修改父節(jié)點(diǎn)的索引記錄，并向上逐級(jí)判斷內(nèi)部節(jié)點(diǎn)是否因?yàn)轫?yè)合并導(dǎo)致索引項(xiàng)不滿足最低要求，刪除結(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é)點(diǎn)仍然滿足要求，刪除結(jié)束            if (leafNode.isValid()) {                LeafNode sibling;                InternalNode parent = leafNode.parent;                // 刪除后，葉子節(jié)點(diǎn)不滿足要求，左兄弟節(jié)點(diǎn)可以移動(dòng)一個(gè)索引項(xiàng)到當(dāng)前葉子節(jié)點(diǎn)                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é)點(diǎn)不滿足要求，右兄弟節(jié)點(diǎn)可以移動(dòng)一個(gè)索引項(xiàng)到當(dāng)前葉子節(jié)點(diǎn)                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é)點(diǎn)不滿足要求，左兄弟節(jié)點(diǎn)可以與當(dāng)前葉子節(jié)點(diǎn)合并                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é)點(diǎn)不滿足要求，右兄弟節(jié)點(diǎn)可以與當(dāng)前葉子節(jié)點(diǎn)合并                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;                    }                    // 逐級(jí)向上層判斷是否滿足要求                    if (parent.isValid()) {                        handleDeficiency(parent);                    }                }                // 刪除后，B+樹(shù)為空                else if (this.root == null && this.head.curNum == 0) {                    this.head = null;                }            }        }    }}/** * 處理不滿足要求的內(nèi)部節(jié)點(diǎn) * @param internalNode */private void handleInvalidInternalNode(InternalNode internalNode) {    InternalNode sibling;    InternalNode parent = internalNode.parent;    // 當(dāng)前內(nèi)部節(jié)點(diǎn)為根節(jié)點(diǎn)    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é)點(diǎn)可以移動(dòng)索引項(xiàng)    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é)點(diǎn)可以移動(dòng)索引項(xiàng)    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é)點(diǎn)可以合并    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é)點(diǎn)可以合并    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+樹(shù)