, V> { // 是否为叶子节点 protected boolean isLeaf; //是否是根节点 protected boolean isRoot; // 父节点 pr_java b+数据落盘">
devbox
笔触狂放9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【大数据存储】Java实现B+树(增、删、单值查询和范围查询)_java b+数据落盘

作者：笔触狂放9 | 2024-08-20 11:50:05

赞

踩

java b+数据落盘

BPlusNode.java

  1. package BplusTree;
  2.  
  3. import java.util.*;
  4.  
  5. @SuppressWarnings("all")
  6. public class BPlusNode<K extends Comparable<K>, V> {
  7.  
  8.     // 是否为叶子节点
  9.     protected boolean isLeaf;
  10.  
  11.     //是否是根节点
  12.     protected boolean isRoot;
  13.  
  14.     // 父节点
  15.     protected BPlusNode<K, V> parent;
  16.  
  17.     // 叶节点的前驱节点
  18.     protected BPlusNode<K, V> previous;
  19.  
  20.     // 叶节点的后继节点
  21.     protected BPlusNode<K, V> next;
  22.  
  23.     // 节点的关键字列表
  24.     protected List<Map.Entry<K, V>> entries;
  25.  
  26.     // 子节点列表
  27.     protected List<BPlusNode<K, V>> children;
  28.  
  29.     //构造方法
  30.     public BPlusNode(boolean isLeaf) {
  31.         this.isLeaf = isLeaf;
  32.         entries = new ArrayList();
  33.         //如果不是叶子结点，则有孩子列表
  34.         if (!isLeaf) {
  35.             children = new ArrayList();
  36.         }
  37.     }
  38.  
  39.     //构造方法
  40.     public BPlusNode(boolean isLeaf, boolean isRoot) {
  41.         this(isLeaf);
  42.         this.isRoot = isRoot;
  43.     }
  44.  
  45.     //单值查找，找到key对应的value值
  46.     public V query(K key) {
  47.         //如果是叶子节点
  48.         if (isLeaf) {
  49.             //二分查找
  50.             int low = 0, high = entries.size() - 1, mid;
  51.             int comp;
  52.             while (low <= high) {
  53.                 mid = (low + high) / 2;
  54.                 comp = entries.get(mid).getKey().compareTo(key);
  55.                 //等于key值
  56.                 if (comp == 0) {
  57.                     //在entries列表中取value值
  58.                     return entries.get(mid).getValue();
  59.                 } else if (comp < 0) {
  60.                     low = mid + 1;
  61.                 } else {
  62.                     high = mid - 1;
  63.                 }
  64.             }
  65.             //未找到所要查询的对象
  66.             return null;
  67.         }
  68.  
  69.         //如果不是叶子节点
  70.         //如果key小于节点最左边的key，沿第一个子节点继续递归地搜索
  71.         if (key.compareTo(entries.get(0).getKey()) < 0) {
  72.             return children.get(0).query(key);
  73.             //如果key大于等于节点最右边的key，沿最后一个子节点继续递归地搜索
  74.         } else if (key.compareTo(entries.get(entries.size() - 1).getKey()) >= 0) {
  75.             return children.get(children.size() - 1).query(key);
  76.             //否则沿比key大的前一个子节点继续递归地搜索
  77.         } else {
  78.             //二分查找
  79.             int low = 0, high = entries.size() - 1, mid = 0;
  80.             int comp;
  81.             while (low <= high) {
  82.                 mid = (low + high) / 2;
  83.                 comp = entries.get(mid).getKey().compareTo(key);
  84.                 if (comp == 0) {
  85.                     return children.get(mid + 1).query(key);
  86.                 } else if (comp < 0) {
  87.                     low = mid + 1;
  88.                 } else {
  89.                     high = mid - 1;
  90.                 }
  91.             }
  92.             return children.get(low).query(key);
  93.         }
  94.     }
  95.  
  96.     //范围查找
  97.     public List<Map.Entry<K, V>> rangeQuery(K startInclude ,K endExclude){
  98.         //如果是叶子结点
  99.         if(isLeaf) {
  100.             //result存放结果
  101.             List<Map.Entry<K, V>> result = new ArrayList<>();
  102.             int start =findIndex(startInclude);
  103.             int end=findIndex(endExclude);
  104.             for(int i=start;i<end;i++) {
  105.                 result.addAll((Collection<? extends Map.Entry<K, V>>) entries.get(i));
  106.             }
  107.             BPlusNode<K,V> nextLeaf = this.next;
  108.             while(nextLeaf!=null){
  109.                 for(int i=0;i<nextLeaf.entries.size();++i){
  110.                     if(nextLeaf.entries.get(i).getKey().compareTo(endExclude)<0){
  111.                         result.addAll((Collection<? extends Map.Entry<K, V>>) nextLeaf.entries.get(i));
  112.                     }
  113.                     else{
  114.                         return result;
  115.                     }
  116.                 }
  117.             }
  118.         }
  119.  
  120.         //如果不是叶子节点
  121.         //如果下界仍小于最左边的key，沿第一个子节点继续递归地搜索
  122.         if (startInclude.compareTo(entries.get(0).getKey()) < 0) {
  123.             return children.get(0).rangeQuery(startInclude,endExclude);
  124.             //如果上界还大于等于节点最右边的key，沿最后一个子节点继续递归地搜索
  125.         } else if (endExclude.compareTo(entries.get(entries.size() - 1).getKey()) >= 0) {
  126.             return children.get(children.size() - 1).rangeQuery(startInclude,endExclude);
  127.             //否则沿比下界大的前一个子节点继续递归地搜索
  128.         } else {
  129.             //二分查找
  130.             int low = 0, high = entries.size() - 1, mid = 0;
  131.             int comp;
  132.             while (low <= high) {
  133.                 mid = (low + high) / 2;
  134.                 comp = entries.get(mid).getKey().compareTo(startInclude);
  135.                 if (comp == 0) {
  136.                     return children.get(mid + 1).rangeQuery(startInclude,endExclude);
  137.                 } else if (comp < 0) {
  138.                     low = mid + 1;
  139.                 } else {
  140.                     high = mid - 1;
  141.                 }
  142.             }
  143.             return children.get(low).rangeQuery(startInclude,endExclude);
  144.         }
  145.     }
  146.  
  147.     //二分查找找到key在entries中的位置
  148.     protected int findIndex(K key) {
  149.         int l = 0;
  150.         int r = entries.size() - 1;
  151.         int index = entries.size();
  152.         while (l <= r) {
  153.             int mid = l + ((r - l) >> 1);
  154.             if (entries.get(mid).getKey().compareTo(key) >= 0) {
  155.                 index = mid;
  156.                 r = mid - 1;
  157.             } else {
  158.                 l = mid + 1;
  159.             }
  160.         }
  161.         return index;
  162.     }
  163.  
  164.     //插入 将key value键值对插入tree
  165.     public void insertOrUpdate(K key, V value, BPlusTree<K, V> tree) {
  166.         //如果是叶子节点
  167.         if (isLeaf) {
  168.             //小于树的度，不需要分裂，直接插入或更新
  169.             if (contains(key) != -1 || entries.size() < tree.getOrder()) {
  170.                 insertOrUpdate(key, value);
  171.                 if (tree.getHeight() == 0) {
  172.                     tree.setHeight(1);
  173.                 }
  174.                 return;
  175.             }
  176.             //需要分裂
  177.             //分裂成左右两个节点
  178.             BPlusNode<K, V> left = new BPlusNode<K, V>(true);
  179.             BPlusNode<K, V> right = new BPlusNode<K, V>(true);
  180.             //设置链接
  181.             if (previous != null) {
  182.                 //前驱结点的next指针指向left
  183.                 previous.next = left;
  184.                 left.previous = previous;
  185.             }
  186.             if (next != null) {
  187.                 //后继结点的pre指针指向right
  188.                 next.previous = right;
  189.                 right.next = next;
  190.             }
  191.             //没有前驱
  192.             if (previous == null) {
  193.                 tree.setHead(left);
  194.             }
  195.             //left的后继指针指向right
  196.             left.next = right;
  197.             //right的前驱指针指向left
  198.             right.previous = left;
  199.             //pre和next置空
  200.             previous = null;
  201.             next = null;
  202.  
  203.             //把原节点关键字复制到到分裂出来的两个新节点
  204.             copy2Nodes(key, value, left, right, tree);
  205.  
  206.             //如果不是根节点
  207.             if (parent != null) {
  208.                 //调整父子节点关系
  209.                 //在父节点的children序列中的位置
  210.                 int index = parent.children.indexOf(this);
  211.                 //移除当前结点
  212.                 parent.children.remove(this);
  213.                 //更新左右新结点的parent
  214.                 left.parent = parent;
  215.                 right.parent = parent;
  216.                 //在父节点的children序列中添加两个新结点
  217.                 parent.children.add(index, left);
  218.                 parent.children.add(index + 1, right);
  219.                 //在父节点的关键字列表的index位置中添加右结点的第一个关键字
  220.                 parent.entries.add(index, right.entries.get(0));
  221.                 entries = null; //删除当前节点的关键字信息
  222.                 children = null; //删除当前节点的孩子节点引用
  223.  
  224.                 //父节点插入或更新关键字
  225.                 parent.updateInsert(tree);
  226.                 parent = null; //删除当前节点的父节点引用
  227.  
  228.                 //如果是根节点
  229.             } else {
  230.                 isRoot = false;
  231.                 //新建根节点
  232.                 BPlusNode<K, V> parent = new BPlusNode<K, V>(false, true);
  233.                 tree.setRoot(parent);
  234.                 //把相应的指针和序列更新
  235.                 left.parent = parent;
  236.                 right.parent = parent;
  237.                 parent.children.add(left);
  238.                 parent.children.add(right);
  239.                 parent.entries.add(right.entries.get(0));
  240.                 entries = null;
  241.                 children = null;
  242.             }
  243.             return;
  244.  
  245.         }
  246.         //如果不是叶子节点
  247.         //如果key小于等于节点最左边的key，沿第一个子节点继续递归地搜索
  248.         if (key.compareTo(entries.get(0).getKey()) < 0) {
  249.             children.get(0).insertOrUpdate(key, value, tree);
  250.             //如果key大于节点最右边的key，沿最后一个子节点继续递归地搜索
  251.         } else if (key.compareTo(entries.get(entries.size() - 1).getKey()) >= 0) {
  252.             children.get(children.size() - 1).insertOrUpdate(key, value, tree);
  253.             //否则沿比key大的前一个子节点继续递归地搜索
  254.         } else {
  255.             //二分查找
  256.             int low = 0, high = entries.size() - 1, mid = 0;
  257.             int comp;
  258.             while (low <= high) {
  259.                 mid = (low + high) / 2;
  260.                 comp = entries.get(mid).getKey().compareTo(key);
  261.                 if (comp == 0) {
  262.                     children.get(mid + 1).insertOrUpdate(key, value, tree);
  263.                     break;
  264.                 } else if (comp < 0) {
  265.                     low = mid + 1;
  266.                 } else {
  267.                     high = mid - 1;
  268.                 }
  269.             }
  270.             if (low > high) {
  271.                 children.get(low).insertOrUpdate(key, value, tree);
  272.             }
  273.         }
  274.     }
  275.  
  276.     //把原节点关键字复制到到分裂出来的两个新节点
  277.     private void copy2Nodes(K key, V value, BPlusNode<K, V> left,
  278.                             BPlusNode<K, V> right, BPlusTree<K, V> tree) {
  279.         //左右两个节点关键字长度，比方说原结点有5个数，则left分2个，right分3个
  280.         int leftSize = (tree.getOrder() + 1) / 2 + (tree.getOrder() + 1) % 2;
  281.         boolean b = false;//用于记录新元素是否已经被插入
  282.         for (int i = 0; i < entries.size(); i++) {
  283.             //左结点
  284.             if (leftSize != 0) {
  285.                 leftSize--;
  286.                 if (!b && entries.get(i).getKey().compareTo(key) > 0) {
  287.                     //在左节点的entries序列中新建一个存放新元素
  288.                     left.entries.add(new AbstractMap.SimpleEntry<K, V>(key, value));
  289.                     b = true;
  290.                     i--;
  291.                 } else {
  292.                     left.entries.add(entries.get(i));
  293.                 }
  294.                 //右结点
  295.             } else {
  296.                 if (!b && entries.get(i).getKey().compareTo(key) > 0) {
  297.                     //在右节点的entries序列中新建一个存放新元素
  298.                     right.entries.add(new AbstractMap.SimpleEntry<K, V>(key, value));
  299.                     b = true;
  300.                     i--;
  301.                 } else {
  302.                     right.entries.add(entries.get(i));
  303.                 }
  304.             }
  305.         }
  306.         //新元素仍没插入，说明新元素最大，把它放在右节点
  307.         if (!b) {
  308.             right.entries.add(new AbstractMap.SimpleEntry<K, V>(key, value));
  309.         }
  310.     }
  311.  
  312.     /**
  313.      * 插入节点后中间节点的更新
  314.      */
  315.     protected void updateInsert(BPlusTree<K, V> tree) {
  316.  
  317.         //如果子节点数超出阶数，则需要分裂该节点
  318.         if (children.size() > tree.getOrder()) {
  319.             //分裂成左右两个节点
  320.             BPlusNode<K, V> left = new BPlusNode<K, V>(false);
  321.             BPlusNode<K, V> right = new BPlusNode<K, V>(false);
  322.             //左右两个节点子节点的长度
  323.             int leftSize = (tree.getOrder() + 1) / 2 + (tree.getOrder() + 1) % 2;
  324.             int rightSize = (tree.getOrder() + 1) / 2;
  325.             //复制子节点到分裂出来的新节点，并更新关键字
  326.             for (int i = 0; i < leftSize; i++) {
  327.                 left.children.add(children.get(i));
  328.                 //把每个孩子的parent指针指向left
  329.                 children.get(i).parent = left;
  330.             }
  331.             for (int i = 0; i < rightSize; i++) {
  332.                 right.children.add(children.get(leftSize + i));
  333.                 //把每个孩子的parent指针指向right
  334.                 children.get(leftSize + i).parent = right;
  335.             }
  336.             for (int i = 0; i < leftSize - 1; i++) {
  337.                 //更新左节点的entries列表
  338.                 left.entries.add(entries.get(i));
  339.             }
  340.             for (int i = 0; i < rightSize - 1; i++) {
  341.                 //更新右节点的entries列表
  342.                 right.entries.add(entries.get(leftSize + i));
  343.             }
  344.  
  345.             //如果不是根节点
  346.             if (parent != null) {
  347.                 //调整父子节点关系
  348.                 int index = parent.children.indexOf(this);
  349.                 //在父节点的children列表中移除当前结点
  350.                 parent.children.remove(this);
  351.                 //更新指针指向
  352.                 left.parent = parent;
  353.                 right.parent = parent;
  354.                 //更新列表
  355.                 parent.children.add(index, left);
  356.                 parent.children.add(index + 1, right);
  357.                 parent.entries.add(index, entries.get(leftSize - 1));
  358.                 //原来的置空
  359.                 entries = null;
  360.                 children = null;
  361.  
  362.                 //递归调用  父节点更新关键字
  363.                 parent.updateInsert(tree);
  364.                 parent = null;
  365.                 //如果是根节点
  366.             } else {
  367.                 isRoot = false;
  368.                 //新建根节点
  369.                 BPlusNode<K, V> parent = new BPlusNode<K, V>(false, true);
  370.                 tree.setRoot(parent);
  371.                 tree.setHeight(tree.getHeight() + 1);
  372.                 //更新
  373.                 left.parent = parent;
  374.                 right.parent = parent;
  375.                 parent.children.add(left);
  376.                 parent.children.add(right);
  377.                 parent.entries.add(entries.get(leftSize - 1));
  378.                 //原来的置空
  379.                 entries = null;
  380.                 children = null;
  381.             }
  382.         }
  383.     }
  384.  
  385.     /**
  386.      * 删除节点后中间节点的更新
  387.      */
  388.     protected void updateRemove(BPlusTree<K, V> tree) {
  389.  
  390.         // 如果子节点数小于M / 2或者小于2，则需要合并节点
  391.         if (children.size() < tree.getOrder() / 2 || children.size() < 2) {
  392.             if (isRoot) {
  393.                 // 如果是根节点并且子节点数大于等于2，无需合并
  394.                 if (children.size() >= 2) return;
  395.                 // 否则与子节点合并
  396.                 //新建根节点
  397.                 BPlusNode<K, V> root = children.get(0);
  398.                 tree.setRoot(root);
  399.                 tree.setHeight(tree.getHeight() - 1);
  400.                 root.parent = null;
  401.                 root.isRoot = true;
  402.                 //原来的置空
  403.                 entries = null;
  404.                 children = null;
  405.                 return;
  406.             }
  407.             //计算前后节点
  408.             //当前结点在父节点的children序列中的位置
  409.             int currIdx = parent.children.indexOf(this);
  410.             int prevIdx = currIdx - 1;
  411.             int nextIdx = currIdx + 1;
  412.             //新建前驱和后继
  413.             BPlusNode<K, V> previous = null, next = null;
  414.             if (prevIdx >= 0) {
  415.                 previous = parent.children.get(prevIdx);
  416.             }
  417.             if (nextIdx < parent.children.size()) {
  418.                 next = parent.children.get(nextIdx);
  419.             }
  420.  
  421.             // 如果前驱节点子节点数大于M / 2并且大于2，则从其处借补
  422.             if (previous != null
  423.                     && previous.children.size() > tree.getOrder() / 2
  424.                     && previous.children.size() > 2) {
  425.                 //前驱叶子节点末尾节点添加到首位
  426.                 int idx = previous.children.size() - 1;
  427.                 //新建借的结点
  428.                 BPlusNode<K, V> borrow = previous.children.get(idx);
  429.                 //借走了，从前驱结点的children序列中移除
  430.                 previous.children.remove(idx);
  431.                 //借过来了，更新相关
  432.                 borrow.parent = this;
  433.                 children.add(0, borrow);
  434.                 int preIndex = parent.children.indexOf(previous);
  435.  
  436.                 entries.add(0, parent.entries.get(preIndex));
  437.                 parent.entries.set(preIndex, previous.entries.remove(idx - 1));
  438.                 return;
  439.             }
  440.  
  441.             // 同理，如果后继节点子节点数大于M / 2并且大于2，则从其处借补
  442.             if (next != null
  443.                     && next.children.size() > tree.getOrder() / 2
  444.                     && next.children.size() > 2) {
  445.                 //后叶子节点首位添加到末尾
  446.                 BPlusNode<K, V> borrow = next.children.get(0);
  447.                 next.children.remove(0);
  448.                 borrow.parent = this;
  449.                 children.add(borrow);
  450.                 int preIndex = parent.children.indexOf(this);
  451.                 entries.add(parent.entries.get(preIndex));
  452.                 parent.entries.set(preIndex, next.entries.remove(0));
  453.                 return;
  454.             }
  455.  
  456.             // 如果前驱结点不够借，就同前驱节点合并
  457.             if (previous != null
  458.                     && (previous.children.size() <= tree.getOrder() / 2
  459.                     || previous.children.size() <= 2)) {
  460.                 for (int i = 0; i < children.size(); i++) {
  461.                     previous.children.add(children.get(i));
  462.                 }
  463.                 for (int i = 0; i < previous.children.size(); i++) {
  464.                     previous.children.get(i).parent = this;
  465.                 }
  466.                 int indexPre = parent.children.indexOf(previous);
  467.                 previous.entries.add(parent.entries.get(indexPre));
  468.                 for (int i = 0; i < entries.size(); i++) {
  469.                     previous.entries.add(entries.get(i));
  470.                 }
  471.                 children = previous.children;
  472.                 entries = previous.entries;
  473.  
  474.                 //更新父节点的关键字列表
  475.                 parent.children.remove(previous);
  476.                 previous.parent = null;
  477.                 previous.children = null;
  478.                 previous.entries = null;
  479.                 //合并了，父节点的孩子就少一个
  480.                 parent.entries.remove(parent.children.indexOf(this));
  481.                 if ((!parent.isRoot
  482.                         && (parent.children.size() >= tree.getOrder() / 2
  483.                         && parent.children.size() >= 2))
  484.                         || parent.isRoot && parent.children.size() >= 2) {
  485.                     return;
  486.                 }
  487.                 //递归调用
  488.                 parent.updateRemove(tree);
  489.                 return;
  490.             }
  491.  
  492.             // 同理，后继结点不够借，就同后面节点合并
  493.             if (next != null
  494.                     && (next.children.size() <= tree.getOrder() / 2
  495.                     || next.children.size() <= 2)) {
  496.                 for (int i = 0; i < next.children.size(); i++) {
  497.                     BPlusNode<K, V> child = next.children.get(i);
  498.                     children.add(child);
  499.                     child.parent = this;
  500.                 }
  501.                 int index = parent.children.indexOf(this);
  502.                 entries.add(parent.entries.get(index));
  503.                 for (int i = 0; i < next.entries.size(); i++) {
  504.                     entries.add(next.entries.get(i));
  505.                 }
  506.                 parent.children.remove(next);
  507.                 next.parent = null;
  508.                 next.children = null;
  509.                 next.entries = null;
  510.                 parent.entries.remove(parent.children.indexOf(this));
  511.                 if ((!parent.isRoot && (parent.children.size() >= tree.getOrder() / 2
  512.                         && parent.children.size() >= 2))
  513.                         || parent.isRoot && parent.children.size() >= 2) {
  514.                     return;
  515.                 }
  516.                 parent.updateRemove(tree);
  517.                 return;
  518.             }
  519.         }
  520.     }
  521.  
  522.     //在叶子中删除key
  523.     public V remove(K key, BPlusTree<K, V> tree) {
  524.         //如果是叶子节点
  525.         if (isLeaf) {
  526.             //如果不包含该关键字，则直接返回
  527.             if (contains(key) == -1) {
  528.                 return null;
  529.             }
  530.             //如果既是叶子节点又是根节点，直接删除
  531.             if (isRoot) {
  532.                 if (entries.size() == 1) {
  533.                     tree.setHeight(0);
  534.                 }
  535.                 return remove(key);
  536.             }
  537.             //如果关键字数大于M / 2，直接删除
  538.             if (entries.size() > tree.getOrder() / 2 && entries.size() > 2) {
  539.                 return remove(key);
  540.             }
  541.             //如果自身关键字数小于M / 2，并且前驱节点关键字数大于M / 2，则从其处借补
  542.             if (previous != null &&
  543.                     previous.parent == parent
  544.                     && previous.entries.size() > tree.getOrder() / 2
  545.                     && previous.entries.size() > 2) {
  546.                 //添加到首位
  547.                 int size = previous.entries.size();
  548.                 entries.add(0, previous.entries.remove(size - 1));
  549.                 int index = parent.children.indexOf(previous);
  550.                 parent.entries.set(index, entries.get(0));
  551.                 return remove(key);
  552.             }
  553.             //如果自身关键字数小于M / 2，并且后节点关键字数大于M / 2，则从其处借补
  554.             if (next != null
  555.                     && next.parent == parent
  556.                     && next.entries.size() > tree.getOrder() / 2
  557.                     && next.entries.size() > 2) {
  558.                 entries.add(next.entries.remove(0));
  559.                 int index = parent.children.indexOf(this);
  560.                 parent.entries.set(index, next.entries.get(0));
  561.                 return remove(key);
  562.             }
  563.  
  564.             //前驱不够借，就同前面节点合并
  565.             if (previous != null
  566.                     && previous.parent == parent
  567.                     && (previous.entries.size() <= tree.getOrder() / 2
  568.                     || previous.entries.size() <= 2)) {
  569.                 V returnValue = remove(key);
  570.                 for (int i = 0; i < entries.size(); i++) {
  571.                     //将当前节点的关键字添加到前节点的末尾
  572.                     previous.entries.add(entries.get(i));
  573.                 }
  574.                 entries = previous.entries;
  575.                 parent.children.remove(previous);
  576.                 previous.parent = null;
  577.                 previous.entries = null;
  578.                 //更新链表
  579.                 if (previous.previous != null) {
  580.                     BPlusNode<K, V> temp = previous;
  581.                     temp.previous.next = this;
  582.                     previous = temp.previous;
  583.                     temp.previous = null;
  584.                     temp.next = null;
  585.                 } else {
  586.                     tree.setHead(this);
  587.                     previous.next = null;
  588.                     previous = null;
  589.                 }
  590.                 parent.entries.remove(parent.children.indexOf(this));
  591.                 if ((!parent.isRoot && (parent.children.size() >= tree.getOrder() / 2
  592.                         && parent.children.size() >= 2))
  593.                         || parent.isRoot && parent.children.size() >= 2) {
  594.                     return returnValue;
  595.                 }
  596.                 //父节点要调整
  597.                 parent.updateRemove(tree);
  598.                 return returnValue;
  599.             }
  600.             //后继结点不够借，就同后面节点合并
  601.             if (next != null
  602.                     && next.parent == parent
  603.                     && (next.entries.size() <= tree.getOrder() / 2
  604.                     || next.entries.size() <= 2)) {
  605.                 V returnValue = remove(key);
  606.                 for (int i = 0; i < next.entries.size(); i++) {
  607.                     //从首位开始添加到末尾
  608.                     entries.add(next.entries.get(i));
  609.                 }
  610.                 next.parent = null;
  611.                 next.entries = null;
  612.                 parent.children.remove(next);
  613.                 //更新链表
  614.                 if (next.next != null) {
  615.                     BPlusNode<K, V> temp = next;
  616.                     temp.next.previous = this;
  617.                     next = temp.next;
  618.                     temp.previous = null;
  619.                     temp.next = null;
  620.                 } else {
  621.                     next.previous = null;
  622.                     next = null;
  623.                 }
  624.                 //更新父节点的关键字列表
  625.                 parent.entries.remove(parent.children.indexOf(this));
  626.                 if ((!parent.isRoot && (parent.children.size() >= tree.getOrder() / 2
  627.                         && parent.children.size() >= 2))
  628.                         || parent.isRoot && parent.children.size() >= 2) {
  629.                     return returnValue;
  630.                 }
  631.                 parent.updateRemove(tree);
  632.                 return returnValue;
  633.             }
  634.         }
  635.         /*如果不是叶子节点*/
  636.  
  637.         //如果key小于等于节点最左边的key，沿第一个子节点继续搜索
  638.         if (key.compareTo(entries.get(0).getKey()) < 0) {
  639.             return children.get(0).remove(key, tree);
  640.             //如果key大于节点最右边的key，沿最后一个子节点继续搜索
  641.         } else if (key.compareTo(entries.get(entries.size() - 1).getKey()) >= 0) {
  642.             return children.get(children.size() - 1).remove(key, tree);
  643.             //否则沿比key大的前一个子节点继续搜索
  644.         } else {
  645.             //二分查找
  646.             int low = 0, high = entries.size() - 1, mid = 0;
  647.             int comp;
  648.             while (low <= high) {
  649.                 mid = (low + high) / 2;
  650.                 comp = entries.get(mid).getKey().compareTo(key);
  651.                 if (comp == 0) {
  652.                     return children.get(mid + 1).remove(key, tree);
  653.                 } else if (comp < 0) {
  654.                     low = mid + 1;
  655.                 } else {
  656.                     high = mid - 1;
  657.                 }
  658.             }
  659.             return children.get(low).remove(key, tree);
  660.         }
  661.     }
  662.  
  663.     // 判断当前节点是否包含该关键字
  664.     protected int contains(K key) {
  665.         int low = 0, high = entries.size() - 1, mid;
  666.         int comp;
  667.         while (low <= high) {
  668.             mid = (low + high) / 2;
  669.             comp = entries.get(mid).getKey().compareTo(key);
  670.             if (comp == 0) {
  671.                 return mid;
  672.             } else if (comp < 0) {
  673.                 low = mid + 1;
  674.             } else {
  675.                 high = mid - 1;
  676.             }
  677.         }
  678.         return -1;
  679.     }
  680.  
  681.     // 插入到当前节点的关键字中
  682.     protected void insertOrUpdate(K key, V value) {
  683.         //二叉查找，插入
  684.         int low = 0, high = entries.size() - 1, mid;
  685.         int comp;
  686.         while (low <= high) {
  687.             mid = (low + high) / 2;
  688.             comp = entries.get(mid).getKey().compareTo(key);
  689.             if (comp == 0) {
  690.                 entries.get(mid).setValue(value);
  691.                 break;
  692.             } else if (comp < 0) {
  693.                 low = mid + 1;
  694.             } else {
  695.                 high = mid - 1;
  696.             }
  697.         }
  698.         if (low > high) {
  699.             entries.add(low, new AbstractMap.SimpleEntry<K, V>(key, value));
  700.         }
  701.     }
  702.  
  703.     // 返回待删除节点的value值
  704.     protected V remove(K key) {
  705.         int low = 0, high = entries.size() - 1, mid;
  706.         int comp;
  707.         while (low <= high) {
  708.             mid = (low + high) / 2;
  709.             comp = entries.get(mid).getKey().compareTo(key);
  710.             if (comp == 0) {
  711.                 return entries.remove(mid).getValue();
  712.             } else if (comp < 0) {
  713.                 low = mid + 1;
  714.             } else {
  715.                 high = mid - 1;
  716.             }
  717.         }
  718.         return null;
  719.     }
  720.  
  721.     public String toString() {
  722.         StringBuilder sb = new StringBuilder();
  723.         sb.append("isRoot: ");
  724.         sb.append(isRoot);
  725.         sb.append(", ");
  726.         sb.append("isLeaf: ");
  727.         sb.append(isLeaf);
  728.         sb.append(", ");
  729.         sb.append("keys: ");
  730.         for (Map.Entry<K, V> entry : entries) {
  731.             sb.append(entry.getKey());
  732.             sb.append(", ");
  733.         }
  734.         sb.append(", ");
  735.         return sb.toString();
  736.     }
  737.  
  738.     //打印信息
  739.     public void printBPlusTree(int index) {
  740.         if (this.isLeaf) {
  741.             System.out.print("层级：" + index + ",叶子节点，keys为: ");
  742.             for (int i = 0; i < entries.size(); ++i)
  743.                 System.out.print(entries.get(i) + " ");
  744.             System.out.println();
  745.         } else {
  746.             System.out.print("层级：" + index + ",非叶子节点，keys为: ");
  747.             for (int i = 0; i < entries.size(); ++i)
  748.                 System.out.print(entries.get(i) + " ");
  749.             System.out.println();
  750.             for (int i = 0; i < children.size(); ++i)
  751.                 children.get(i).printBPlusTree(index + 1);
  752.         }
  753.     }
  754. }
  755.

BPlusTree.java

  1. package BplusTree;
  2.  
  3. /**
  4.  * B+树的定义：
  5.  * 1.任意非叶子结点最多有M个子节点；且M>2；M为B+树的阶数
  6.  * 2.除根结点以外的非叶子结点至少有 (M+1)/2个子节点；
  7.  * 3.根结点至少有2个子节点；
  8.  * 4.除根节点外每个结点存放至少（M-1）/2和至多M-1个关键字；（至少1个关键字）
  9.  * 5.非叶子结点的子树指针比关键字多1个；
  10.  * 6.非叶子节点的所有key按升序存放，假设节点的关键字分别为K[0], K[1] … K[M-2],指向子女的指针分别为P[0], P[1]…P[M-1]。则有：
  11.  * 　　　P[0] < K[0] <= P[1] < K[1] …..< K[M-2] <= P[M-1]
  12.  * 7.所有叶子结点位于同一层；
  13.  * 8.为所有叶子结点增加一个链指针；
  14.  * 9.所有关键字都在叶子结点出现
  15.  */
  16.  
  17. @SuppressWarnings("all")
  18. public class BPlusTree<K extends Comparable<K>, V> {
  19.  
  20.     // 根节点
  21.     protected BPlusNode<K, V> root;
  22.  
  23.     // 每个空间最多可以存多少数据
  24.     protected int order;
  25.  
  26.     // 叶子节点的链表头
  27.     protected BPlusNode<K, V> head;
  28.  
  29.     // 树高
  30.     protected int height = 0;
  31.  
  32.     public BPlusNode<K, V> getHead() {
  33.         return head;
  34.     }
  35.  
  36.     public void setHead(BPlusNode<K, V> head) {
  37.         this.head = head;
  38.     }
  39.  
  40.     public BPlusNode<K, V> getRoot() {
  41.         return root;
  42.     }
  43.  
  44.     public void setRoot(BPlusNode<K, V> root) {
  45.         this.root = root;
  46.     }
  47.  
  48.     public int getOrder() {
  49.         return order;
  50.     }
  51.  
  52.     public void setOrder(int order) {
  53.         this.order = order;
  54.     }
  55.  
  56.     public void setHeight(int height) {
  57.         this.height = height;
  58.     }
  59.  
  60.     public int getHeight() {
  61.         return height;
  62.     }
  63.  
  64.     public V query(K key) {return root.query(key);}
  65.  
  66.     public V remove(K key) {
  67.         return root.remove(key, this);
  68.     }
  69.  
  70.     public void insertOrUpdate(K key, V value) {
  71.         root.insertOrUpdate(key, value, this);
  72.     }
  73.  
  74.     public BPlusTree(int order) {
  75.         if (order < 3) {
  76.             System.out.print("度数要大于2！");
  77.             System.exit(0);
  78.         }
  79.         this.order = order;
  80.         root = new BPlusNode<K, V>(true, true);
  81.         head = root;
  82.     }
  83.  
  84.     public void printBPlusTree() {
  85.         this.root.printBPlusTree(0);
  86.     }
  87. }
  88.

BPlusTreeTest.java

  1. package BplusTree;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.List;
  5. import java.util.Random;
  6.  
  7. public class BPlusTreeTest {
  8.     // 测试
  9.     public static void main(String[] args) {
  10.         int size = 12;
  11.         int order = 4;
  12.        testRandomInsert(size, order);
  13.        //testRandomSearch(size, order);
  14.        //testRandomRemove(size, order);
  15.     }
  16.  
  17.     private static void testRandomRemove(int size, int order) {
  18.         BPlusTree<Integer, Integer> tree = new BPlusTree<Integer, Integer>(order);
  19.         System.out.println("\nTest random remove " + size + " datas, of order:"
  20.                 + order);
  21.         Random random = new Random();
  22.         boolean[] a = new boolean[size + 10];
  23.         List<Integer> list = new ArrayList<Integer>();
  24.         int randomNumber = 0;
  25.         System.out.println("Begin random insert...");
  26.         for (int i = 0; i < size; i++) {
  27.             randomNumber = random.nextInt(size);
  28.             a[randomNumber] = true;
  29.             list.add(randomNumber);
  30.             tree.insertOrUpdate(randomNumber, randomNumber);
  31.         }
  32.         tree.printBPlusTree();
  33.         System.out.println("Begin random remove...");
  34.         long current = System.currentTimeMillis();
  35.         for (int j = 0; j < size; j++) {
  36.             randomNumber = list.get(j);
  37.             if (a[randomNumber]) {
  38.                 if (tree.remove(randomNumber) == null) {
  39.                     System.err.println("得不到数据:" + randomNumber);
  40.                     break;
  41.                 } else {
  42.                     a[randomNumber] = false;
  43.                 }
  44.             }
  45.         }
  46.         long duration = System.currentTimeMillis() - current;
  47.         System.out.println("time elpsed for duration: " + duration);
  48.         tree.printBPlusTree();
  49.         System.out.println("树高："+tree.getHeight());
  50.     }
  51.  
  52.     private static void testRandomSearch(int size, int order) {
  53.         BPlusTree<Integer, Integer> tree = new BPlusTree<Integer, Integer>(order);
  54.         System.out.println("\nTest random search " + size + " datas, of order:"
  55.                 + order);
  56.         Random random = new Random();
  57.         boolean[] a = new boolean[size + 10];
  58.         int randomNumber = 0;
  59.         System.out.println("Begin random insert...");
  60.         for (int i = 0; i < size; i++) {
  61.             randomNumber = random.nextInt(size);
  62.             a[randomNumber] = true;
  63.             tree.insertOrUpdate(randomNumber, randomNumber);
  64.         }
  65.         tree.printBPlusTree();
  66.         System.out.println("Begin random search...");
  67.         long current = System.currentTimeMillis();
  68.         for (int j = 0; j < size; j++) {
  69.             randomNumber = random.nextInt(size);
  70.             if (a[randomNumber]) {
  71.                 if (tree.query(randomNumber) == null) {
  72.                     System.err.println("得不到数据:" + randomNumber);
  73.                     break;
  74.                 }
  75.             }
  76.         }
  77.         long duration = System.currentTimeMillis() - current;
  78.         System.out.println("time elpsed for duration: " + duration);
  79.     }
  80.  
  81.     private static void testRandomInsert(int size, int order) {
  82.         BPlusTree<Integer, Integer> tree = new BPlusTree<Integer, Integer>(order);
  83.         System.out.println("\nTest random insert " + size + " datas, of order:"
  84.                 + order);
  85.         Random random = new Random();
  86.         int randomNumber = 0;
  87.  
  88.         for (int i = 0; i < size; i++) {
  89.             randomNumber = random.nextInt(size * 10);
  90.             System.out.print(randomNumber + " ");
  91.             tree.insertOrUpdate(randomNumber, randomNumber);
  92.         }
  93.  
  94.         tree.printBPlusTree();
  95.         System.out.println("树高："+tree.getHeight());
  96.     }
  97. }
  98.

 

 

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/1007022
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号