手撕B树

落日映苍穹つ 2022-02-24 12:05 286阅读 0赞

### 手撕B树 ###

*   *  B树
     *  特点
     *  结构图
     *  构造B树
     *  代码实现
     *  完整代码

## B树 ##

B树和B+树都是多路查找树。具备分支多层数少的优点常用于数据库索引存储  
BTree大量应用在数据库（mongodb）和文件系统当中，B+Tree经常用于数据库索引（空间局部性原理）  
B树代表每个节点可存储的数据节点不超过m-1，且每个节点的子节点不超过m个的树。根节点的子节点为0或至少为2  
B+树与B树区别就是B+树只在没有子节点的底层节点存储数据而其他包含子节点的父节点都是不存储数据值存储索引值  
假设m为4我们就说这是一颗4叉的B树，其每个节点可以存储最多3个数据节点，最多含有4个子节点

## 特点 ##

数据保存在节点  
一个节点可以至有多m-1个数据节点  
根结点如果有子女则至少有两个子女  
除根结点以外的所有结点（不包括叶子结点）的度数正好是当前结点保存的数据节点总数加1，故内部子树个数 k 满足：┌m/2┐ <= k <= m  
所有的叶子结点都位于同一层。（叶子节点指的是指向null）  
每个非根节点所包含的数据节点个数 j 满足：┌m/2┐ - 1 <= j <= m - 1；// ┌m/2┐ ==》m/2向上取整

## 结构图 ##

![b-tree][]

## 构造B树 ##

我们先了解下其几点重要构建要求  
1.保持所有的叶子结点都位于同一层  
2.一个节点可以至有多m-1个数据节点  
3.每个非根节点所包含的数据节点个数 j 满足：┌m/2┐ - 1 <= j <= m - 1；// ┌m/2┐ ==》m/2向上取整  
基于这些条件，B树的插入是从底部插入，先假设可以直接插入找到的节点，这时不破坏要求1  
插入后因为新增数据节点如果破坏了要求2，进行裂变  
裂变为了满足要求3从中间裂变  
裂变出来的节点插入当前结点父节点（递归操作），因为是向上裂变插入，所以不破坏规则1

## 代码实现 ##

可以保存多个数据节点的节点类

class MultiNode{ 
    		int nodeCounter = 0;//数据节点总数
    		Node head;//数据节点链表头
    		Node tail;//数据节点链表尾
    		MultiNode parent;//父节点
    		Node greaterParent;//大于当前节点的数据节点
    		Node lesserParent;//小于当前节点的数据节点
    	}

数据节点类

class Node{ 
    		int num;//索引大小
    		MultiNode greater;//大于
    		MultiNode lesser;//小于
    		Node prev;
    		Node next;
    	}

裂变操作

private Node fissAndReturnBreakNode(MultiNode multiNode,int breakPoint) { 
    		if(breakPoint<1 || breakPoint>=multiNums) { 
    			return null;
    		}
    		//裂变
    		if(multiNode.greaterParent!=null) { 
    			//父节点断开
    			multiNode.greaterParent.lesser = null;
    			multiNode.greaterParent = null;
    		}
    		if(multiNode.lesserParent!=null) { 
    			//父节点断开
    			multiNode.lesserParent.greater = null;
    			multiNode.lesserParent = null;
    		}
    		Node beakNode = multiNode.head;
    		for(int i=0;i<breakPoint;i++)
    			beakNode = beakNode.next;
    		MultiNode newMultiNode = new MultiNode();
    		newMultiNode.head = beakNode.next;
    		newMultiNode.tail = multiNode.tail;
    		multiNode.tail = beakNode.prev;
    		newMultiNode.nodeCounter = multiNode.nodeCounter - breakPoint -1;
    		multiNode.nodeCounter = breakPoint;
    		beakNode.next = beakNode.prev = newMultiNode.head.prev = multiNode.tail.next = null;
    		if(beakNode.lesser!=null) { 
    			beakNode.lesser.lesserParent = multiNode.tail;
    			multiNode.tail.greater = beakNode.lesser;
    		}
    		if(beakNode.greater!=null) { 
    			beakNode.greater.greaterParent = newMultiNode.head;
    			newMultiNode.head.lesser = beakNode.greater;
    		}
    		beakNode.lesser = multiNode;
    		multiNode.greaterParent = beakNode;
    		beakNode.greater = newMultiNode;
    		newMultiNode.lesserParent = beakNode;
    		newMultiNode.parent = multiNode.parent;
    		return beakNode;
    	}

插入操作

public void addNum(int num) { 
    		Node node = new Node();
    		node.num = num;
    		addNode(node,root);
    	}
    	protected MultiNode addNode(Node node,MultiNode multiNode) { 
    		if(node == null) { 
    			return multiNode;
    		}
    		else if(multiNode == null) { 
    			root = multiNode = new MultiNode();
    			multiNode.tail = multiNode.head = node;
    			multiNode.nodeCounter++;
    			return multiNode;
    		}
    		else{ 
    			Node head = multiNode.head;
    			do{ 
    				if(head.num > node.num) { 
    					if(head.lesser!=null) { 
    						addNode(node,head.lesser);
    					}
    					else { 
    						if(head.prev!=null) { 
    							if(head.lesser != null) { 
    								node.greater = head.lesser;
    								head.lesser.lesserParent = node;
    							}
    							if(head.prev.greater!=null) { 
    								node.lesser = head.prev.greater;
    								head.prev.greater.greaterParent = node;
    							}
    							head.prev.next = node;
    							node.prev = head.prev;
    						}
    						else { 
    							if(head.lesser!=null) { 
    								node.greater = head.lesser;
    								head.lesser.lesserParent = node;
    							}
    							multiNode.head = node;
    						}
    						node.next = head;
    						head.prev = node;
    						if(++multiNode.nodeCounter == multiNums) { 
    							Node breakNode = fissAndReturnBreakNode(multiNode,multiNums/2);
    							addNode(breakNode,multiNode.parent);
    						}
    					}
    					return multiNode;
    				}
    			}while((head = head.next)!=null);
    			
    			if(multiNode.tail.greater!=null) { 
    				addNode(node,multiNode.tail.greater);
    			}
    			else { 
    				multiNode.tail.next = node;
    				node.prev = multiNode.tail;
    				if(multiNode.tail.greater!=null) { 
    					node.lesser = multiNode.tail.greater;
    					multiNode.tail.greater.greaterParent = node;
    				}
    				multiNode.tail = node;
    				if(++multiNode.nodeCounter == multiNums) { 
    					Node breakNode = fissAndReturnBreakNode(multiNode,multiNums/2);
    					addNode(breakNode,multiNode.parent);
    				}
    			}
    			return multiNode;
    		}
    	}

## 完整代码 ##

package zcy;
    
    import java.util.concurrent.LinkedBlockingQueue;
    
    public class BTree { 
    
    	public BTree(int multiNums) { 
    		this.multiNums = multiNums;
    	}
    	
    	volatile MultiNode root;//根节点
    	
    	int multiNums;//叉的数目
    	
    	public static void printTree(MultiNode node) { 
    		if(node == null)
    			return;
    		System.out.println(node+": ");
    		LinkedBlockingQueue<MultiNode> queue = new LinkedBlockingQueue<MultiNode>();
    		Node head = node.head; 
    		while(head!=null) { 
    			if(head.lesser!=null)
    				queue.add(head.lesser);
    			if(head.greater!=null)
    				queue.add(head.greater);
    			System.out.println(head.num+" -> lesser:"+head.lesser+", ->greate:"+head.greater);
    			head = head.next;
    		}
    		System.out.println();
    		queue.forEach(multiNode->printTree(multiNode));
    	}
    	class MultiNode{ 
    		int nodeCounter = 0;//数据节点总数
    		Node head;//数据节点链表头
    		Node tail;//数据节点链表尾
    		MultiNode parent;//父节点
    		Node greaterParent;//大父节点
    		Node lesserParent;//大父节点
    	}
    	
    	class Node{ 
    		int num;//索引大小
    		MultiNode greater;//大于
    		MultiNode lesser;//小于
    		Node prev;
    		Node next;
    	}
    	
    	public void addNum(int num) { 
    		Node node = new Node();
    		node.num = num;
    		addNode(node,root);
    	}
    	
    	private Node fissAndReturnBreakNode(MultiNode multiNode,int breakPoint) { 
    		if(breakPoint<1 || breakPoint>=multiNums) { 
    			return null;
    		}
    		//裂变
    		if(multiNode.greaterParent!=null) { 
    			//父节点断开
    			multiNode.greaterParent.lesser = null;
    			multiNode.greaterParent = null;
    		}
    		if(multiNode.lesserParent!=null) { 
    			//父节点断开
    			multiNode.lesserParent.greater = null;
    			multiNode.lesserParent = null;
    		}
    		Node beakNode = multiNode.head;
    		for(int i=0;i<breakPoint;i++)
    			beakNode = beakNode.next;
    		MultiNode newMultiNode = new MultiNode();
    		newMultiNode.head = beakNode.next;
    		newMultiNode.tail = multiNode.tail;
    		multiNode.tail = beakNode.prev;
    		newMultiNode.nodeCounter = multiNode.nodeCounter - breakPoint -1;
    		multiNode.nodeCounter = breakPoint;
    		beakNode.next = beakNode.prev = newMultiNode.head.prev = multiNode.tail.next = null;
    		if(beakNode.lesser!=null) { 
    			beakNode.lesser.lesserParent = multiNode.tail;
    			multiNode.tail.greater = beakNode.lesser;
    		}
    		if(beakNode.greater!=null) { 
    			beakNode.greater.greaterParent = newMultiNode.head;
    			newMultiNode.head.lesser = beakNode.greater;
    		}
    		beakNode.lesser = multiNode;
    		multiNode.greaterParent = beakNode;
    		beakNode.greater = newMultiNode;
    		newMultiNode.lesserParent = beakNode;
    		newMultiNode.parent = multiNode.parent;
    		return beakNode;
    	}
    	
    	protected MultiNode addNode(Node node,MultiNode multiNode) { 
    		if(node == null) { 
    			return multiNode;
    		}
    		else if(multiNode == null) { 
    			root = multiNode = new MultiNode();
    			multiNode.tail = multiNode.head = node;
    			multiNode.nodeCounter++;
    			return multiNode;
    		}
    		else{ 
    			Node head = multiNode.head;
    			do{ 
    				if(head.num > node.num) { 
    					if(head.lesser!=null) { 
    						addNode(node,head.lesser);
    					}
    					else { 
    						if(head.prev!=null) { 
    							if(head.lesser != null) { 
    								node.greater = head.lesser;
    								head.lesser.lesserParent = node;
    							}
    							if(head.prev.greater!=null) { 
    								node.lesser = head.prev.greater;
    								head.prev.greater.greaterParent = node;
    							}
    							head.prev.next = node;
    							node.prev = head.prev;
    						}
    						else { 
    							if(head.lesser!=null) { 
    								node.greater = head.lesser;
    								head.lesser.lesserParent = node;
    							}
    							multiNode.head = node;
    						}
    						node.next = head;
    						head.prev = node;
    						if(++multiNode.nodeCounter == multiNums) { 
    							Node breakNode = fissAndReturnBreakNode(multiNode,multiNums/2);
    							addNode(breakNode,multiNode.parent);
    						}
    					}
    					return multiNode;
    				}
    			}while((head = head.next)!=null);
    			
    			if(multiNode.tail.greater!=null) { 
    				addNode(node,multiNode.tail.greater);
    			}
    			else { 
    				multiNode.tail.next = node;
    				node.prev = multiNode.tail;
    				if(multiNode.tail.greater!=null) { 
    					node.lesser = multiNode.tail.greater;
    					multiNode.tail.greater.greaterParent = node;
    				}
    				multiNode.tail = node;
    				if(++multiNode.nodeCounter == multiNums) { 
    					Node breakNode = fissAndReturnBreakNode(multiNode,multiNums/2);
    					addNode(breakNode,multiNode.parent);
    				}
    			}
    			return multiNode;
    		}
    	}
    	
    	public static void main(String[] args) { 
    		BTree tree = new BTree(4);//4叉B树每个multi最多含有3个节点
    		for(int i=0;i<7;i++)
    			tree.addNum(i);
    		BTree.printTree(tree.root);
    	}
    
    }

更多文章，请搜索公众号歪歪梯Club  
![更多资料，请搜索公众号编程宝可梦][20200521183346518.jpg]

[b-tree]: /images/20220224/3aed925a5a2042b39e39b78bf50a16af.png
[20200521183346518.jpg]: /images/20220224/be76276ea0e84cfdb6bfe5090e951bfc.png