您现在的位置是：首页 > 文章详情

算法之树（一，B-树原理详解）(Java版)-持续更新补充

日期：2018-08-10点击：437收藏

因为是复习，从基础开始一起复习。
如果冲着标题来的，可以直接跳到后半部分看B树的内容(～￣▽￣)～

支持云栖社区！同时俺也有自己的独立博客——白水东城，因为在社区博客里只能发发技术文章之类的，但在自己博客我会写一些最近随笔和读书笔记等等哈哈，也希望大家能支持一下 ( •̀ ω •́ )y
这里是我独立博客里这篇文章的链接：
算法之树（一，B-树原理详解）(Java版)-持续更新补充

一、二叉树

二叉树的基本操作

public class BinaryTreeNode { private int data; private BinaryTreeNode leftChild; private BinaryTreeNode rightChild; public int getData() { return data; } public void setData(int data) { this.data = data; } public BinaryTreeNode getLeftChild() { return leftChild; } public void setLeftChild(BinaryTreeNode leftChild) { this.leftChild = leftChild; } public BinaryTreeNode getRightChild() { return rightChild; } public void setRightChild(BinaryTreeNode rightChild) { this.rightChild = rightChild; } }

 public class BinaryTree { private BinaryTreeNode root; public BinaryTree() { } public BinaryTree(BinaryTreeNode root) { this.root = root; } public void setRoot(BinaryTreeNode root) { this.root = root; } public BinaryTreeNode getRoot() { return root; } public void clear(BinaryTreeNode node) { if(node != null) { clear(node.getLeftChild()); clear(node.getRightChild()); node = null; } } public void clear() { clear(root); } public boolean isEmpty() { return root == null; } public int height() { return height(root); } public int height(BinaryTreeNode node) { if(node == null) { return 0; }else { int l = height(node.getLeftChild()); int r = height(node.getRightChild()); return l < r ? r + 1 : l + 1; } } public int size() { return size(root); } public int size(BinaryTreeNode node) { if(node == null) { return 0; }else { return 1 + size(node.getLeftChild()) + size(node.getRightChild()); } } public BinaryTreeNode getParent(BinaryTreeNode node) { return (root == null || root == node) ? null : getParent(root, node); } public BinaryTreeNode getParent(BinaryTreeNode subTree, BinaryTreeNode node) { if(subTree == null) { return null; } if(subTree.getLeftChild() == node || subTree.getRightChild() == node) { return subTree; } BinaryTreeNode parent = null; if((parent = getParent(subTree.getLeftChild(),node)) != null) { return parent; }else { return getParent(subTree.getRightChild(), node); } } public BinaryTreeNode getLeftTree(BinaryTreeNode node) { return node.getLeftChild(); } public BinaryTreeNode getRightTree(BinaryTreeNode node) { return node.getRightChild(); } public void insertLeft(BinaryTreeNode parent, BinaryTreeNode newNode) { parent.setLeftChild(newNode); } public void insertRight(BinaryTreeNode parent, BinaryTreeNode newNode) { parent.setRightChild(newNode); } public void visited(BinaryTreeNode node) { } public void preOrder(BinaryTreeNode node) { if(node != null) { visited(node); preOrder(node.getLeftChild()); preOrder(node.getRightChild()); } } public void inOrder(BinaryTreeNode node) { if(node != null) { inOrder(node.getLeftChild()); visited(node); inOrder(node.getRightChild()); } } public void postOrder(BinaryTreeNode node) { if(node != null) { postOrder(node.getLeftChild()); postOrder(node.getRightChild()); visited(node); } } }

二、二叉查找树

简单来说就是左子树结点值都小于根结点，右子树都大于根结点。

二叉查找树的操作

 public class BinarySearchingTree { private BinaryTreeNode root; public BinarySearchingTree(BinaryTreeNode root) { this.root = root; } public BinaryTreeNode search(int data) { return search(root, data); } //二叉查找树的插入操作很简单，找到和待插入结点同样值的结点则不插入， //否则在树的末尾新建一个结点，不需要变动其他结点 public void insert(int data) { if(root == null) { root = new BinaryTreeNode(); root.setData(data); }else { searchAndInsert(null, root, data); } } //如果待删除的结点左右子树都不为空， //则选择右子树的最左结点或者左子树的最右结点来代替 public void delete(int data) { if(root.getData() == data) { root = null; return; } //知道要删除那个结点的父结点很关键 //但无法确定要删除的结点是其父结点的左还是右结点 //需要特别判断一下 BinaryTreeNode parent = searchParent(data); if(parent == null) { return; } BinaryTreeNode node = search(parent, data); if(node.getLeftChild() == null && node.getRightChild() == null) { //叶子结点，直接删除 if(parent.getLeftChild() != null && parent.getLeftChild().getData() == data) { parent.setLeftChild(null); }else { parent.setRightChild(null); } }else if(node.getLeftChild() != null && node.getRightChild() == null) { //左子树不为空 if(parent.getLeftChild()!= null && parent.getLeftChild().getData() ==data) { parent.setLeftChild(node.getLeftChild()); }else { parent.setRightChild(node.getRightChild()); } }else if(node.getLeftChild() == null && node.getClass() != null) { //右子树不为空 if(parent.getLeftChild() != null && parent.getLeftChild().getData() == data) { parent.setLeftChild(node.getRightChild()); }else { parent.setRightChild(node.getRightChild()); } }else { //左右子树都不为空 //查找右子树最左子节点 BinaryTreeNode deleteNode = node; BinaryTreeNode temp = node.getRightChild(); //1. 右子树没有左孩子，直接上移 if(temp.getLeftChild() == null) { temp.setLeftChild(deleteNode.getLeftChild()); }else { while(temp.getLeftChild() != null) { node = temp; temp = temp.getLeftChild(); } //2. 继承节点原右子树上移 node.setLeftChild(temp.getRightChild()); //3. 继承节点就位 temp.setLeftChild(deleteNode.getLeftChild()); temp.setRightChild(deleteNode.getRightChild()); } //4. 更新父节点为删除结点的原父节点 if(parent.getLeftChild() != null && parent.getLeftChild().getData() == data) { parent.setLeftChild(temp); }else { parent.setRightChild(temp); } } } public BinaryTreeNode searchParent(int data) { return searchParent(null, root, data); } public BinaryTreeNode getRoot() { return root; } private BinaryTreeNode searchAndInsert(BinaryTreeNode parent, BinaryTreeNode node, int data) { if(node == null) { node = new BinaryTreeNode(); node.setData(data); if(data > parent.getData()) { parent.setRightChild(node); }else { parent.setLeftChild(node); } return node; }else if(node.getData() == data) { return node; }else if(data > node.getData()) { return searchAndInsert(node, node.getRightChild(), data); }else { return searchAndInsert(node, node.getLeftChild(), data); } } private BinaryTreeNode search(BinaryTreeNode node, int data) { if(node == null) { return null; }else if(node.getData() == data) { return node; }else if(data > node.getData()) { return search(node.getRightChild(), data); }else { return search(node.getLeftChild(), data); } } private BinaryTreeNode searchParent(BinaryTreeNode parent, BinaryTreeNode node, int data) { if(node == null) { return null; }else if(node.getData() == data) { return parent; }else if(data > node.getData()) { return searchParent(node, node.getRightChild(), data); }else { return searchParent(node, node.getLeftChild(), data); } } }

三、平衡二叉树

Balanced Binary Tree，又叫AVL树(由提出者名字缩写而来)。简单来说，在二叉查找树的基础上，要保持左右子树高度差不超过1，我们把左子树高度减去右子树高度叫做平衡因子(Balanced Factor,BF)
二叉查找树查找的时间复杂度最好是O(logn),最坏是O(n)，而AVL最好最坏都是O(logn)，插入和删除也是O(logn)。

代码暂时省略，以后回来补充

四、B-树、B+树

B-树

B减树和B树是一个意思，那个不是减号而是短横。这个不纠结，意思明白就行。
B树是用于在外存工作的平衡搜索树，MySQL中的索引主要是基于hash表或者B+树。

为什么不用二叉查找树？

数据库索引为啥不用二叉查找树实现呢？
二叉查找树的时间复杂度为O(logn)，从算法逻辑上讲查找速度和比较次数都是最小的。但是，现实要考虑 磁盘IO。
数据库索引是存在磁盘上的，因为数据量很大的时候索引大小可能达到几个G。所以在利用索引查询的时候，不能把整个索引全部加载到内存，只有逐一加载每一个磁盘页，这里磁盘页对应着索引树的节点，如图（图片源于程序员小灰）。
此处输入图片的描述

当数据比较大，无法全部存入内存时，需要将部分数据存在外存中，在需要的时候读入内存，修改之后又写回外存。由于外存的速度与内存有几个数量级的差别，所以节省在外存上花的时间，对搜索树的性能提高时最有效的。
最常见的外存就是磁盘。磁盘是块设备，也就是说磁盘的读写单位是以块为单位，一般地块大小从0.5k到4k。即使你只读取一个字节，磁盘也是将包含该字节的所有数据读取到硬盘中。而在磁盘读取过程中，最占用时间的是磁盘的寻道，也就是磁头在盘片上找到需要读取的块所在位置的时间，而在盘片上顺序读取数据的所花的时间是占比比较小的。

要减少外存上花的时间，就可以从减少读盘次数以及减少寻道时间着手。B树采取的方法就是，就充分的利用盘块的空间，在一个盘块中尽可能多的存储信息，或者在连续的盘块地址上存储尽可能多的信息。在数据结构上的变化就是每个节点存储多个key信息以及包含多个子节点。

磁盘的IO次数由树的高度决定的，在最坏的情况下磁盘的IO数等于索引树的高度。而B-树是一棵平衡的m-路查找树，一个m-路查找树，高度为h，每一个节点最多容纳m-1个关键字，所以一棵m-路查找树总共可容纳m^k - 1个关键字。
与二叉查找树比较，当高度为h，能容纳2^h - 1个关键字，高度若为3，则二叉查找树只能容纳7个关键字；而对于200-路查找树可以容纳200^3 - 1个关键字！

再说回来，为了减少磁盘的IO次数，就需要把原来“瘦高”的树结构变得“矮胖”，而这个正满足B树的特征之一。
B树是多路平衡查找树，它的每一个节点最多包含k个孩子，k被称为B树的阶，k的大小取决于磁盘页的大小。就像刚才举例200-路查找树一样。