Published by linzhi teng

March 4th, 2019

树

一. 二叉树

1. 二叉树的基本概念

二叉树是每个结点最多有两个子树的树结构。通常子树被称作"左子树"（left subtree）和"右子树"（right subtree）。

一棵深度为k，且有2^k-1个节点的二叉树，称为满二叉树，这种树的特点是每一层上的节点数都是最大节点数。

1.1 二叉树基本形态

二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：

(1)空二叉树——如图(a)；
(2)只有一个根结点的二叉树——如图(b)；
(3)只有左子树——如图(c)；
(4)只有右子树——如图(d)；
(5)完全二叉树——如图(e)。

注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。
树和二叉树有两个主要差别：

树中结点的最大度数没有限制，而二叉树结点的最大度数为2；

树的结点无左、右之分，而二叉树的结点有左、右之分。

1.2 二叉树类型

(1)完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

(3)平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

1.3 树的相关术语

结点的度：结点子树的个数
树的度：树中最大的结点度。
叶子结点：也叫终端结点，是度为 0 的结点；
分枝结点：度不为0的结点；

1.4 二叉树性质

(1) 在非空二叉树中，第i层的结点总数不超过 2^(i-1)

(2) 深度为h的二叉树最多有 2^h - 1 个结点,最少有h个结点

(3) 对于任意一棵二叉树，如果其叶子结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；

(4)给定N个节点，能构成h(N)种不同的二叉树。
h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)

1.5 二叉树遍历

先序遍历
首先访问根，再先序遍历左（右）子树，最后先序遍历右（左）子树
中序遍历
首先中序遍历左（右）子树，再访问根，最后中序遍历右（左）子树
后序遍历
首先后序遍历左（右）子树，再后序遍历右（左）子树，最后访问根
层次遍历
即按照层次访问，通常用队列来做。访问根，访问子女，再访问子女的子女（越往后的层次越低）（两个子女的级别相同）

2. 完全二叉树

2.1 完全二叉树定义

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

(1)所有的叶结点都出现在第k层或k-l层（层次最大的两层）
(2)对任一结点，如果其右子树的最大层次为L，则其左子树的最大层次为L或L+l。

2.2 完全二叉树性质

假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数， n2是度为2的结点总数， n是结点总数则：

n0=n/2，其中n为奇数时（n1=0）向上取整；n为偶数时（n1=1）。可根据完全二叉树的结点总数计算出叶子结点数。

2.3 完全二叉树特点

完全二叉树的特点是：
(1）只允许最后一层有空缺结点且空缺在右边，即叶子结点只能在层次最大的两层上出现；
(2）对任一结点，如果其右子树的深度为j，则其左子树的深度必为j或j+1。即度为1的点只有1个或0个

2.4 完全二叉树存储

出于简便起见,完全二叉树通常采用数组而不是链表存储
其存储结构如下:
var tree:array[1..n]of longint;{n:integer;n>=1}
对于tree[i]，有如下特点：
（1）若i为奇数且i>1，那么tree的左兄弟为tree[i-1]；
（2）若i为偶数且i （3）若i>1，tree的父亲节点为tree[i/2]；
（4）若2* i<=n，那么tree的左孩子为tree[2* i];若2* i+1<=n,那么tree的右孩子为tree[2* i+1]；
（5）若i>n/2,那么tree[i]为叶子结点（对应于（3））；
（6）若i<(n-1)/2.那么tree[i]必有两个孩子（对应于（4））。
（7）满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

2.5 完全二叉树判定

判断一棵树是否是完全二叉树的思路
1>如果树为空，则直接返回错
2>如果树不为空：层序遍历二叉树
　　 2.1>如果一个结点左右孩子都不为空，则pop该节点，将其左右孩子入队列；
　　 2.1>如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树；
　　 2.2>如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空；则该节点之后的队列中的结点都为叶子节点；该树才是完全二叉树，否则就不是完全二叉树；

3. 满二叉树

3.1 满二叉树定义

对于国内的满二叉树
1. 一个层数为k 的满二叉树总结点数为：2^k - 1,因此满二叉的结点树一定是奇数个。
2. 第i层上的结点数为：2^i -1 ;
3. 一个层数为k的满二叉树的叶子结点个数（也就是最后一层）:2^(k-1) ;
对于国外的满二叉树
满二叉树的任意节点，要么度为0，要么度为2.换个说法即要么为叶子结点，要么同时具有左右孩子。

4. 堆

4.1 堆的概念

堆是具有以下性质的完全二叉树：

每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆

在一个堆有序的二叉树中，父节点的位置是K/2,它的两个子节点的位置是2k,2k+1。

4.2 堆的实现


//最大堆
public class MaxPQ {
    private List arr;      //定义一个数组
    private  int N;                   //定义队列中的元素个数

    public MaxPQ() {
        arr = new ArrayList();
        arr.add(1);
        N = 0;
    }

    public boolean isEmpty() {                   //方法，返回队列是否为空
        return N == 0;                                              
    }

    public int size() {                                 //方法，返回队列中元素的个数
        return N;
    }

    public void inSert(int number) {       //添加方法，添加元素到结合末尾，并且使用上浮方法到指定的位置
        arr.add(number);
        swim(++N);
    }

    public int deleteMax() {                //删除方法，删除最大元素并把最小的元素放到第一个，然后使用下浮方法
        int max = arr.get(1);
        int min  = arr.get(N);
        arr.set(1, min);
        arr.remove(N--);
        sink(1);
        return max;
    }
    //上浮
    public void swim(int N) {
        while(N > 1 && (arr.get(N/2) < arr.get(N))){
            int max = arr.get(N);
            int min = arr.get(N/2);
            arr.set(N,min );
            arr.set(N/2, max);
            N = N/2;
        }
    }
    //下沉
    public void sink(int number) {
        while(number*2 <= N) {
            int index = number*2;
            if(index < N && (arr.get(index) < arr.get(index + 1))) {
                index++;
            }
            if(!(arr.get(number) < arr.get(index))) {
                break;
            }
            int max = arr.get(index);
            int min = arr.get(number);
            arr.set(number, max);
            arr.set(index, min);
            number = index;
        }

    }

    @Override
    public String toString() {
        return "MaxPQ [arr=" + arr + ", N=" + N + "]";
    }
}

5. 二叉查找树(排序树)(Binary Search Tree，BST)

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根节点点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的节点。

例子：

二叉查找树例题

二叉树查找树的详细解析

6. 平衡二叉树(AVL树)

6.1 平衡二叉树定义

对于一般的二叉搜索树（Binary Search Tree），其期望高度（即为一棵平衡树时）为logN，其各操作的时间复杂度（O(logN)）同时也由此而决定。但是，在某些极端的情况下（如在插入的序列是有序的时），二叉搜索树将退化成近似链或链，此时，其操作的时间复杂度将退化成线性的，即O(n)。
为了解决这个问题，要加上一个称为平衡的附加结构条件即：任何结点的深度不得过深
（子树高度相差不超过1），就是平衡二叉树（Balanced Binary Tree），它是G.M. Adelson-Velsky 和 E.M. Landis在1962年在论文中发表的，因此又叫AVL树。
AVL树只是实现平衡二叉树的一种方法，它还有很多的其他实现方法如红黑树、替罪羊树、Treap、伸展树等

6.2 平衡二叉树性质

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个差值也称为平衡因子（其取值可以是1，0，-1，平衡因子是某个结点左右子树层数的差值)

6.3 平衡二叉树的设计

理解了平衡二叉树的概念后，我们在思考一下，那些操作可能引起平衡发生变化呢？
显然只有那些引起结点数量变化的操作才可能导致平衡被改变，也就是删除和插入操作了。
实际上也总是可以通过对树进行简单的修复来让其重新恢复到平衡，而这样的简单操作我们就称之为旋转，当然旋转也有单旋转和双旋转之分。
无论是插入还是删除，只有那些从插入点或者删除点到根结点的路径上的结点的平衡才有可能被改变，因为只有这些结点的子树才可能发生变化，所以最终也只需针对这些点进行平衡修复操作即可。

如何通过旋转来修复一棵失衡的二叉树，这里假设结点X是失衡点，它必须重新恢复平衡，由于任意结点的孩子结点最多有两个，而且导致失衡的必要条件是X结点的两棵子树高度差为2(大于1)，因此一般只有以下4种情况可能导致X点失去平衡：
① 在结点X的左孩子结点的左子树中插入元素
② 在结点X的左孩子结点的右子树中插入元素
③ 在结点X的右孩子结点的左子树中插入元素
④ 在结点X的右孩子结点的右子树中插入元素
以上4种情况，其中第①情况和第④情况是对称的，可以通过单旋转来解决，而第②种情况和第③情况是对称的，需要双旋转来解决。

6.3.1 左左单旋转(LL)情景①分析

在结点X的左孩子结点的左子树中插入元素

6.3.2 右右单旋转(RR)情景④分析

在结点X的右孩子结点的右子树中插入元素

6.3.3 左右双旋转(LR)情景②分析

在结点X的左孩子结点的右子树中插入元素

6.3.4 右左双旋转(RL)情景③分析

在结点X的右孩子结点的左子树中插入元素

平衡二叉树详细解析

二 . 红黑树

1. 红黑树简介

红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:

节点是红色或黑色。
根节点是黑色。
每个叶子节点都是黑色的空节点（NIL节点）。
每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

2. 红黑树的修正

变色、左旋、右旋是红黑树在二叉树上的扩展操作，同时也是基于这三个操作才能遵守红黑树的五个特性。

2.1 左旋

    /*
     * 左旋做了三件事：

     * 1. 将y的左子节点赋给x的右子节点,并将x赋给y左子节点的父节点(y左子节点非空时)

     * 2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右)

     * 3. 将y的左子节点设为x，将x的父节点设为y

     */
    public void leftRotate(RBNode x) {
        if (x == null) return;
        //1. 将y的左子节点赋给x的右子节点,并将x赋给y左子节点的父节点(y左子节点非空时)
        RBNode y = x.right;
        x.right = y.left;
        if (y.left != null) {
            y.left.parent = x;
        }
        //2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右)
        y.parent = x.parent;
        if (x.parent == null) {
            this.mRoot = y;
        } else {
            if (x == x.parent.left) {
                x.parent.left = y;
            } else {
                x.parent.right = y;
            }
        }
        //3. 将y的左子节点设为x，将x的父节点设为y
        y.left = x;
        x.parent = y;
    }

2.2 右旋

/*      右旋做了三件事：
     * 1. 将x的右子节点赋给y的左子节点,并将y赋给x右子节点的父节点(x右子节点非空时)
     * 2. 将y的父节点p(非空时)赋给x的父节点，同时更新p的子节点为x(左或右)
     * 3. 将x的右子节点设为y，将y的父节点设为x
     */
   public void rightRotate(RBNode y) {
        if (y == null) return;
        //1. 将x的右子节点赋给y的左子节点,并将y赋给x右子节点的父节点(x右子节点非空时)
        RBNode x = y.left;
        y.left = x.right;
        if (x.right != null) {
            x.right.parent = y;
        }
        //2. 将y的父节点p(非空时)赋给x的父节点，同时更新p的子节点为x(左或右)
        x.parent = y.parent;
        if (y.parent == null) {
            this.mRoot = x;
        } else {
            if (y == y.parent.left) {
                y.parent.left = x;
            } else {
                y.parent.right = x;
            }
        }
        //3. 将x的右子节点设为y，将y的父节点设为x
        x.right = y;
        y.parent = x;
    }

3. 红黑树节点的添加

红黑树的第 5 条特征规定，任一节点到它子树的每个叶子节点的路径中都包含同样数量的黑节点。也就是说当我们往红黑树中插入一个黑色节点时，会违背这条特征。
同时第 4 条特征规定红色节点的左右孩子一定都是黑色节点，当我们给一个红色节点下插入一个红色节点时，会违背这条特征。
因此我们需要在插入黑色节点后进行结构调整，保证红黑树始终满足这 5 条特征。

3.1 红黑树插入后节点的调整思想:

插入黑色节点的时候担心违背第5条，插入红色节点时担心违背第4条，所以我们将将插入的节点改为红色，然后判断插入的节点的父亲是不是红色，是的话进行修改调整（变色、左旋、右旋）。同时在调整的过程中我们需要遵守5条特性。

新插入的节点是红色的，插入修复操作如果遇到父节点的颜色为黑则修复操作结束。也就是说，只有在父节点为红色节点的时候是需要插入修复操作的。
插入修复操作分为以下的三种情况，而且新插入的节点的父节点都是红色的：

叔叔节点也为红色。
叔叔节点为空，且祖父节点、父节点和新节点处于一条斜线上。
叔叔节点为空，且祖父节点、父节点和新节点不处于一条斜线上。

3.1.1 插入操作-case 1(叔叔节点也为红色)

叔叔节点也为红色。
case 1的操作是将 父节点和叔叔节点 与 祖父节点 的颜色互换，这样就符合了RBTRee的定义。即维持了高度的平衡，修复后颜色也符合RBTree定义的第三条和第四条。下图中，操作完成后A节点变成了新的节点。如果A节点的父节点不是黑色的话，则继续做修复操作。

3.1.2 插入操作-case 2

叔叔节点为空，且祖父节点、父节点和新节点处于一条斜线上。
case 2的操作是：

B和C都是左节点，将B节点进行右旋操作，并且和父节点A互换颜色。通过该修复操作RBTRee的高度和颜色都符合红黑树的定义。
如果B和C节点都是右节点的话，只要将操作变成B节点左旋就可以了。

3.1.3 插入操作-case 3

叔叔节点为空，且祖父节点、父节点和新节点不处于一条斜线上。
case 3的操作是：

C是右节点，将C节点进行左旋，这样就从case 3转换成case 2了，然后针对case 2进行操作处理就行了。case2操作C节点做了一个右旋操作和颜色互换来达到目的。
如果C是左节点，将C节点进行右旋，转换成case2，再左旋就可以了。

4. 红黑树节点的删除

如果删除节点的左孩子和右孩子不同时为null，那么只需要让其子树继承删除该节点的位置
如果删除的节点是叶子节点，我们直接进行调整；
假如删除节点的左右孩子都不是null，需要后继节点替换被删除的节点和值和颜色，这样才不会引起红黑树平衡的破坏，只需要对后继节点删除后进行调整，这样我们就回归处理情况 1 和 2 的状态；
1. 后继节点为左子树最右边的子叶节点
2. 后继节点为右子树最左边的叶子节点；
3. 如果需要删除的节点颜色为红色，那么红黑树的结构不被破坏，也就不需要进行调整。如果我们判断删除节点的颜色为黑色，那么就进行调整；

4.1 红黑树删除之节点调整

调整思想：
为了保证删除节点的父节点左右两边黑色节点数一致，需要重点关注父节点没删除的那一边节点是不是黑色。

如果删除后父亲节点另一边比删除的一边黑色多，就要想办法搞到平衡。
- 1、把父亲节点另一边（即删除节点的兄弟树）其中一个节点弄成红色，也少了一个黑色。
- 2、或者把另一边多的节点（染成黑色）转过来一个

删除修复操作是针对删除黑色节点才有的，当黑色节点被删除后会让整个树不符合RBTree的定义的第四条。

当前节点是黑色的，且兄弟节点是红色的（那么父节点和兄弟节点的子节点肯定是黑色的）；
当前节点是黑色的，且兄弟节点是黑色的，
1）、兄弟节点的两个子节点均为黑色的；
2）、兄弟节点的左子节点是红色，右子节点时黑色的；
3）、兄弟节点的右子节点是红色，左子节点任意颜色；

4.1.1 删除操作-case 1

待删除的节点的兄弟节点是红色的节点。

将父节点涂红，将兄弟节点涂黑，然后将当前节点的父节点进行支点左旋。
case 1这样转换之后就会变成后面的case 2，case 3，或者case 4进行处理了。

4.1.2 删除操作-case 2

待删除的节点的兄弟节点是黑色的节点，且兄弟节点的子节点都是黑色的。

将兄弟节点涂红，将当前节点指向其父节点，将其父节点指向当前节点的祖父节点，继续往树根递归判断以及调整；

4.1.3 删除操作-case 3

待调整的节点的兄弟节点是黑色的节点，且和兄弟节点在一条斜线上的子节点也是黑色，另一个子节点是红色。

把当前节点的兄弟节点涂红，把兄弟节点的左子节点涂黑，然后以兄弟节点作为支点做右旋操作。

case 3的删除操作是一个中间步骤，它的目的是将左边的红色节点借调过来，这样就可以转换成case 4

4.1.4 删除操作-case 4

待调整的节点的兄弟节点是黑色的节点，且和兄弟节点在一条斜线上的子节点是红色，另一个子节点任意

把兄弟节点涂成父节点的颜色，再把父节点涂黑，把兄弟节点的右子节点涂黑，然后以当前节点的父节点为支点做左旋操作。

三 . B树、B+树、B*树

3.1 B树(B-树)

3.1.1 B树简介

B-树是一种多路搜索树（并不一定是二叉的）
1970年，R.Bayer和E.mccreight提出了一种适用于外查找的树，它是一种平衡的多叉树，称为B树（或B-树、B_树）。

B-Tree的接点结构B-tree中，每个结点包含：

本结点所含关键字的个数；
指向父结点的指针；
关键字；
指向子结点的指针数组；

一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树，或者是满足下列性质的树：
1、根结点至少有两个子女；
2、每个非根节点所包含的关键字个数 j 满足：m/2 - 1 <= j <= m - 1；
3、除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加1，故内部子树个数 k 满足：m/2 <= k <= m ；
4、所有的叶子结点都位于同一层。

3.1.2 B树特点

是一种多路搜索树（并不是二叉的）：

定义任意非叶子结点最多只有M个儿子；且M>2；
根结点的儿子数为[2, M]；
除根结点以外的非叶子结点的儿子数为[M/2, M]；
每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
非叶子结点的关键字个数=指向儿子的指针个数-1；
非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
所有叶子结点位于同一层；

3.1.3 B树的查找

在B-树中查找给定关键字的方法类似于二叉排序树上的查找。不同的是在每个结点上确定向下查找的路径不一定是二路而是keynum+1路的。
对结点内的存放有序关键字序列的向量key[l..keynum] 用顺序查找或折半查找方法查找。

若在某结点内找到待查的关键字K，则返回该结点的地址及K在key[1..keynum]中的位置；
否则，确定K在某个key[i]和key[i+1]之间结点后，从磁盘中读son[i]所指的结点继续查找。直到在某结点中查找成功；或直至找到叶结点且叶结点中的查找仍不成功时，查找过程失败。

查找操作的时间开销

B-树上的查找有两个基本步骤：

在B-树中查找结点，该查找涉及读盘DiskRead操作，属外查找；
在结点内查找，该查找属内查找。

查找操作的时间为：

外查找的读盘次数不超过树高h，故其时间是O(h)；
内查找中，每个结点内的关键字数目keynum

注意：

实际上外查找时间可能远远大于内查找时间。
B-树作为数据库文件时，打开文件之后就必须将根结点读人内存，而直至文件关闭之前，此根一直驻留在内存中，故查找时可以不计读入根结点的时间。

3.1.4 B树的插入

插入一个元素时：

首先判断在B树中是否存在，如果不存在，即在叶子结点处结束，然后在叶子结点中插入该新的元素

注意：
1.1 如果叶子结点空间足够，这里需要向右移动该叶子结点中大于新插入关键字的元素，

1.2 如果叶子节点空间满了以致没有足够的空间去添加新的元素，则将该结点进行"分裂"，将一半数量的关键字元素分裂到新的其相邻右结点中，中间关键字元素上移到父结点中（当然，如果父结点空间满了，也同样需要"分裂"操作），而且当结点中关键元素向右移动了，相关的指针也需要向右移。
1.3 如果在根结点插入新元素，空间满了，则进行分裂操作，这样原来的根结点中的中间关键字元素向上移动到新的根结点中，因此导致树的高度增加一层。

3.1.5 B树的删除

首先查找B树中需删除的元素,如果该元素在B树中存在，则将该元素在其结点中进行删除，
如果删除该元素后，首先判断该元素是否有左右孩子结点，如果有，则上移孩子结点中的某相近元素到父节点中，然后是移动之后的情况；如果没有，直接删除后，移动之后的情况。

3.2 B+树

3.2.1 B+树简介

B+ 树是一种树数据结构，是一个n叉树，每个节点通常有多个孩子。
一棵B+树包含根节点、内部节点和叶子节点。根节点可能是一个叶子节点，也可能是一个包含两个或两个以上孩子节点的节点。

B+树用途

B+ 树通常用于数据库和操作系统的文件系统中。NTFS, ReiserFS, NSS, XFS, JFS, ReFS 和BFS等文件系统都在使用B+树作为元数据索引。B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入。

3.2.2 B+树定义

B+树是应文件系统所需而出的一种B-树的变型树。

一棵m阶的B+树和m阶的B-树的差异在于：
1.有n棵子树的结点中含有n个关键字，每个关键字不保存数据，只用来索引，所有数据都保存在叶子节点。
2.所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的非终端结点可以看成是索引部分，结点中仅含其子树（根结点）中的最大（或最小）关键字。
通常在B+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。

B+树与B-树的不同

B+树是B-树的变体，也是一种多路搜索树：

定义基本与B-树同，除了：
叶子结点的子树指针与关键字个数相同；
叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；
为所有叶子结点增加一个链指针；
所有关键字都在叶子结点出现；

3.2.3 B+树的特性：

所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
不可能在非叶子结点命中；
非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
更适合文件索引系统；

3.2.4 B+树 vs B树

为什么说B+-tree比B 树更适合实际应用中操作系统的文件索引和数据库索引？

B+-tree的磁盘读写代价更低
B+-tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B+ 树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。
B+-tree的查询效率更加稳定
由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

3.3 B*树

3.3.1 B*树简介

是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；
B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）；

3.3.2 B*树 vs B+树

B+树的分裂：
当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；
B*树的分裂：
当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；

所以，B*树分配新结点的概率比B+树要低，空间使用率更高；

3.4 小结：

B-树：
多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；
所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；

B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；
B+树总是到叶子结点才命中；

B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；

四. LSM树

4.1 LSM由来

B+树最大的性能问题是会产生大量的随机IO，随着新数据的插入，叶子节点会慢慢分裂，逻辑上连续的叶子节点在物理上往往不连续，甚至分离的很远，但做范围查询时，会产生大量读随机IO。

对于大量的随机写也一样，举一个插入key跨度很大的例子，如7->1000->3->2000 ... 新插入的数据存储在磁盘上相隔很远，会产生大量的随机写IO.

从上面可以看出，低下的磁盘寻道速度严重影响性能（近些年来，磁盘寻道速度的发展几乎处于停滞的状态）。

为了克服B+树的弱点，HBase引入了LSM树的概念，即Log-Structured Merge-Trees。

4.2 LSM树原理

为了更好的说明LSM树的原理，下面举个比较极端的例子：

现在假设有1000个节点的随机key，对于磁盘来说，肯定是把这1000个节点顺序写入磁盘最快，但是这样一来，读就悲剧了，因为key在磁盘中完全无序，每次读取都要全扫描；
那么，为了让读性能尽量高，数据在磁盘中必须得有序，这就是B+树的原理，但是写就悲剧了，因为会产生大量的随机IO，磁盘寻道速度跟不上。

LSM树本质上就是在读写之间取得平衡，和B+树相比，它牺牲了部分读性能，用来大幅提高写性能。

原理

它的原理是把一颗大树拆分成N棵小树，它首先写入到内存中（内存没有寻道速度的问题，随机写的性能得到大幅提升），在内存中构建一颗有序小树，随着小树越来越大，内存的小树会flush到磁盘上。当读时，由于不知道数据在哪棵小树上，因此必须遍历所有的小树，但在每颗小树内部数据是有序的。

实现

以上就是LSM树最本质的原理，有了原理，再看具体的技术就很简单了。

1）首先说说为什么要有WAL（Write Ahead Log），很简单，因为数据是先写到内存中，如果断电，内存中的数据会丢失，因此为了保护内存中的数据，需要在磁盘上先记录logfile，当内存中的数据flush到磁盘上时，就可以抛弃相应的Logfile。

2）什么是memstore, storefile？很简单，上面说过，LSM树就是一堆小树，在内存中的小树即memstore，每次flush，内存中的memstore变成磁盘上一个新的storefile。

3）为什么会有compact？很简单，随着小树越来越多，读的性能会越来越差，因此需要在适当的时候，对磁盘中的小树进行merge，多棵小树变成一颗大树。

Shu

linzhi's Site

树