数据结构

BST树（二叉搜索树）

性质

如果左子树不为空，那么左子树上所有节点的值都小于当前节点
如果右子树不为空，那么右子树上所有节点的值都大于当前节点

AVL树（平衡二叉树）

性质

在BST树的基础上引入了平衡因子的概念，要求任意一个节点的左右子树高度差不超过1

需要旋转的四种情况

左孩子左子树太高：右旋
右孩子右子树太高：左旋
左孩子右子树太高：先对左孩子左旋，再对当前节点右旋（左平衡）
右孩子左子树太高：先对右孩子右旋，再对当前节点左旋（右平衡）

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

// 定义节点类型
template<typename T>
struct Node {
    Node(T data = T()) : data_(data), left_(nullptr), right_(nullptr), height_(1) {}
    T data_;
    Node* left_;
    Node* right_;
    int height_; // 记录节点的高度
};

// AVL树
template<typename T>
class AVLTree {
public:
    AVLTree() : root_(nullptr) {}
    // 插入
    void insert(const T& val) {
        root_ = insert(root_,val);
    }
    // 删除
    void remove(const T& val) {
        root_ = remove(root_,val);
    }
private:
    Node<T>* root_; // 根节点
    // 返回节点的高度
    int height(Node<T> *node) {
        return node == nullptr ? 0 : node->height_;
    }
    // 右旋
    Node<T>* rightRotate(Node<T>* node);
    // 左旋
    Node<T>* leftRotate(Node<T>* node);
    // 左平衡
    Node<T>* leftBalance(Node<T>* node);
    // 右平衡
    Node<T>* rightBalance(Node<T>* node);
    // 插入
    Node<T>* insert(Node<T>* node, const T& val);
    // 删除
    Node<T>* remove(Node<T>* node, const T& val);
};

// 右旋
template<typename T>
Node<T>* AVLTree<T>::rightRotate(Node<T>* node) {
    // 节点旋转
    Node<T>* child = node->left_;
    node->left_ = child->right_;
    child->right_ = node;
    // 高度更新
    node->height_ = max(height(node->left_), height(node->right_)) + 1;
    child->height_ = max(height(child->left_), height(child->right_)) + 1;
    // 返回旋转后的子树的新根节点
    return child;
}

// 左旋
template<typename T>
Node<T>* AVLTree<T>::leftRotate(Node<T>* node) {
    // 节点旋转
    Node<T> *child = node->left_;
    node->right_ = child->left_;
    child->left_ = node;
    // 高度更新
    node->height_ = max(height(node->left_), height(node->right_)) + 1;
    child->height_ = max(height(child->left_), height(child->right_)) + 1;
    // 返回旋转后的子树的新根节点
    return child;
}

// 左平衡 先对node的左子树左旋，再对node右旋
template<typename T>
Node<T>* AVLTree<T>::leftBalance(Node<T> *node) {
    node->left_ = leftRotate(node->left_);
    return rightRotate(node);
}

// 右平衡 先对node的右子树右旋，再对node左旋
template<typename T>
Node<T>* AVLTree<T>::rightBalance(Node<T> *node) {
    node->right_ = rightRotate(node->right_);
    return leftRotate(node);
}

// 插入
template<typename T>
Node<T>* AVLTree<T>::insert(Node<T> *node, const T &val) {
    // 递归结束 找到插入的位置
    if (node == nullptr) return new Node<T>(val);

    if (node->data_ > val) {
        node->left_ = insert(node->left_,val);
        // 判断是否失衡
        if (height(node->left_) - height(node->right_) > 1) {
            if (height(node->left_->left_) >= height(node->left_->right_)) {
                // 左孩子的左子树太高
                node = rightRotate(node);
            } else {
                // 左孩子的右子树太高
                node = leftBalance(node);
            }
        }
    } else if (node->data_ < val) {
        node->right_ = insert(node->right_,val);
        if (height(node->right_) - height(node->left_) > 1) {
            if (height(node->right_->right_) >= height(node->right_->left_)) {
                node = leftRotate(node);
            } else {
                node = rightBalance(node);
            }
        }
    } else {
        // 找到相同节点 不需要向下递归 直接向上回溯
    }

    // 因为子树添加了新的节点 所以在递归的时候需要更新节点高度
    node->height_ = max(height(node->left_), height(node->right_)) + 1;

    return node;
}

// 删除操作 从叶子节点中选出一个节点 进行替换
template<typename T>
Node<T>* AVLTree<T>::remove(Node<T> *node, const T &val) {
    if (node == nullptr) {
        return nullptr;
    }

    if (node->data_ > val) {
        node->left_ = remove(node->left_,val);
        if (height(node->right_) - height(node->left_) > 1) {
            if (height(node->right_->right_) >= height(node->right_->left_)) {
                node = leftRotate(node);
            } else {
                node = rightBalance(node);
            }
        }
    } else if (node->data_ < val) {
        node->right_ = remove(node->right_,val);
        if (height(node->left_) - height(node->right_) > 1) {
            if (height(node->left_->left_) >= height(node->left_->right_)) {
                node = rightRotate(node);
            } else {
                node = leftBalance(node);
            }
        }
    } else {
        // 找到节点
        // 如果有两个孩子
        if (node->left_ != nullptr && node->right_ != nullptr) {
            // 谁高删谁的节点
            if (height(node->left_) >= height(node->right_)) {
                Node<T>* pre = node->left_;
                while (pre->right_ != nullptr) {
                    pre = pre->right_;
                }
                node->data_ = pre->data_;
                node->left_ = remove(node->left_,pre->data_);
            } else {
                Node<T>* pre = node->right_;
                while (pre->left_ != nullptr) {
                    pre = pre->left_;
                }
                node->data_ = pre->data_;
                node->right_ = remove(node->right_,pre->data_);
            }
        } else {
            // 如果只有一个孩子
            if (node->left_ != nullptr) {
                Node<T>* left = node->left_;
                delete node;
                return left;
            } else if (node->right_ != nullptr) {
                Node<T>* right = node->right_;
                delete node;
                return right;
            } else {
                delete node;
                return nullptr;
            }
        }
    }

    // 更新节点高度
    node->height_ = max(height(node->left_), height(node->right_)) + 1;
    return node;
}

性能分析

AVL树插入一个节点最多只需要两次旋转就可以恢复平衡

插入一个节点会导致节点所在的子树高度加1，但是旋转会让新节点所在子树减1，所以AVL树插入一个节点最多只需要两次旋转就可以了

AVL树删除一个节点最多需要O(logN)次旋转才可以恢复平衡

删除一个节点会导致节点所在子树减1，旋转又会让节点所在的子树减1，所以最坏的时候需要O(logN)次旋转

删除节点 X 之后，R4的平衡因子变为 -2，R4 左旋；R3 的平衡因子变为 2，R3 右旋；R2 的平衡因子变为 -2， R2左旋；R1的平衡因子变为2，R1 右旋

当从根节点至待删除节点的父节点平衡因子交替为 -1 和 +1，删除该节点一旦触发旋转就需要logn次旋转

红黑树

红黑树的用途非常广泛，像在map\epoll\定时器\Nginx\CFS\内存管理中都使用了红黑树对节点进行管理

红黑树是一颗接近平衡的二叉搜索树，没有AVL树的平衡因子概念，只是靠满足五条性质维持接近平衡的结构，保证最长路径不超过最短路径的2倍

适用于需要排序的场景下，红黑树不需要像二叉搜索树在极端情况下形成链表导致O(n)的时间复杂度，又不需要像平衡搜索树在维持树的平衡上面过多的性能消耗

性质

节点是红色或者黑色的
根是黑色的
叶子节点都是黑色（叶子节点是指最底层的空节点，null节点）
红节点的子节点都是黑色的
- 红节点的父节点是黑色的
- 从根节点到叶子节点的路径上不会存在两个连续的红节点
从任意节点到其每个叶子节点的所有路径都包含相同数目的黑节点

左旋右旋

左旋：

将y原来的左子树接到x的右子树下
将y的父节点指向x的父节点，x的父节点原来指向x改为指向y
将x接到y的左子树节点下

右旋：

将x原来的右子树接到y的左子树下
将x的父节点指向y的父节点，y的父节点原来指向y改为指向x
将y接到x的右子树节点下

代码实现

// 左旋
void leftRotate(RbTree *T, RbTreeNode *x) {
    RbTreeNode *y = x->right;

    // 1.将y原来的左子树接到x的右子树下
    x->right = y->left;
    if (y->left != T->nil) {
        y->left->parent = x;
    }

    // 2.将y的父节点指向x的父节点,x的父节点原来指向x改为指向y
    y->parent = x->parent;
    if (x->parent == T->nil) {
        // 此时Y是根节点
        T->root = y;
    } else if (x == x->parent->left) {
        x->parent->left = y;
    } else {
        x->parent->right = y;
    }

    // 3.将x接到y的左子树下
    y->left = x;
    x->parent = y;
}

// 右旋
void rightRotate (RbTree *T, RbTreeNode *y) {
    RbTreeNode* x = y->left;

    // 1.将x原来的右子树接到y的左子树下
    y->left = x->right;
    if (x->right != T->nil) {
        x->right->parent = y;
    }

    // 2.将x的父节点指向y的父节点，y的父节点原来指向y改为指向x
    x->parent = y->parent;
    if (y->parent == T->nil) {
        T->root = x;
    } else if (y->parent->left == y) {
        y->parent->left = x;
    } else {
        y->parent->right = x;
    }

    // 3.将y接到x的右子树下
    x->right = y;
    y->parent = x;
}

左旋右旋的代码中只不过left和right交换，x和y交换，其他都一样

增加节点

全部都添加到叶子节点中，最后再去调整

增加的节点默认是红色的，不会去影响路径上黑色节点的数量

原因：避免每一次加入都需要去旋转

void rbTreeInsert(RbTree *T, RbTreeNode *newNode) {
    RbTreeNode* node = T->root;
    RbTreeNode* parent = T->nil;

    // 寻找可以插入的位置 找到叶子节点
    while (node != T->nil) {
        parent = node;
        if (newNode->key < node->key) {
            node = node->left
        } else if (newNode->key > node->key) {
            node = node->right;
        } else {
            return; // 具体相同的值要不要改动看需求
        }
    }

    newNode->parent = parent;
    if (parent == T->nil) {
        T->root = newNode;
    } else if (parent->key > newNode->key) {
        parent->left = newNode;
    } else {
        parent->right = newNode;
    }
    newNode->left = T->nil;
    newNode->right = T->nil;
    newNode->color = RED;

    rbTreeInsertFixup(T,newNode);
}

树的调整

当父节点为红色节点的时候就需要调整，因为违反了规则四

调整的过程中会遇到三种情况：

叔父节点是红色
叔父节点是黑色，当前节点父节点是左子树
叔父节点是黑色，当前节点父节点是右子树

如果叔父节点是红色那么在左右不需要区分，没有什么区别，到时候祖父节点改为红色，父节点和叔父节点改为黑色继续向上调整

但是如果是黑色就需要区分了，因为父节点和祖父节点颜色的时候会导致黑色路径高度发生变化

目前已知的情况：

当前节点是红色
父节点是红色
祖父节点是黑色

叔父节点是红色的

将父亲和叔父都改为黑色，此时黑色路径长度发生变化，需要将祖父改为红色

从祖父开始继续向上调整

父亲是祖父的左孩子

自己是父亲的左孩子：

将父亲变为黑色，此时左边黑色路径发生变化，需要将祖父改为红色

此时右子树黑色路径减少，需要对祖父右旋，将父节点成为新祖父恢复右子树的黑色高度

自己是父亲的右孩子：

将父亲左旋变为父亲是自己的左孩子，就变成上面的情况了

父亲是祖父的右孩子

自己是父亲的右孩子：

将父亲变为黑色，此时右边黑色路径变长，将祖父变为红色

此时左边黑色路径变短，进行左旋恢复左子树高度

自己是父亲的左孩子：

对父亲进行右旋让父亲成为自己的右孩子变成上面的情况

// 调整树
void rbTreeInsertFixup(RbTree *T, RbTreeNode *node) {
    // 如果父节点是黑色的则不需要调整
    while (node->parent->color == RED) {
        // 父节点是祖父节点的左子树
        if (node->parent == node->parent->parent->left) {
            // 叔父节点
            RbTreeNode *uncle = node->parent->parent->right;
            if (uncle->color == RED) {
                // 将父节点改为黑色和叔父节点改为黑色，祖父节点改为红色继续向上调整就可以了
                // 会影响到黑色路径的长度
                node->parent->color = BLACK;
                uncle->color = BLACK;
                node->parent->parent->color = RED;
                // 继续向上调整
                node = node->parent->parent;
            } else {
                if (node == node->parent->right) {
                    // 左旋
                    node = node->parent;
                    leftRotate(T,node);
                }
                // 让父节点变为黑色，祖父节点变为红色（右子树的黑色高度变低了）
                // 对祖父右旋，让父节点成为新祖父，恢复右子树的高度
                // 这种情况只需要两次旋转就可以完成调整了
                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                rightRotate(T,node->parent->parent);
            }
        } else {
            RbTreeNode *uncle = node->parent->parent->left;
            if (uncle->color == RED) {
                node->parent->color = BLACK;
                uncle->color = BLACK;
                node->parent->parent->color = RED;
                node = node->parent->parent;
            } else {
                if (node == node->parent->left) {
                    node = node->parent;
                    rightRotate(T,node);
                }
                // 左子树的高度减小了
                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                leftRotate(T,node->parent->parent);
            }
        }
    }

    T->root->color = BLACK;
}

删除节点

定义三种节点：

覆盖节点Z：被指定删除的结点，实际上是通过被覆盖实现
删除节点Y：实际上被删除的节点，一般是后继节点
轴心节点X：维护红黑树的节点

删除的节点可能有三种情况：

没有左右子树：直接删除
有且只有一颗子树：将该节点的唯一子树挂到父节点上，然后删除该节点
左右子树都有：找一个后继节点Y覆盖指定节点Z，然后删除节点Y，Y是情况1或2中的一种

如果当前结点是父结点的左子树的情况，可以归纳出来四种情况。同理如果当前结点是父结点的右子树，我们也可以归纳出来四种情况。但是这四种情况的差异就是旋转方向的区别而已（镜像的）。一共是8种情况，但是归纳出来其实是4种

当前节点是父节点的左子树

情况一：当前节点的兄弟节点是红色

将兄弟变为黑色，父亲变为红色，此时左边高度降低，对父节点左旋恢复左子树高度，此时兄弟的左孩子变为新的兄弟，变为情况2、3、4

（因为要让x的兄弟是黑色，所以只能从左右侄子中获得）

情况二：兄弟为黑色，左右侄子也是黑色

此时兄弟和自己都是黑色，父节点为红色或黑色

将兄弟变为红色，轴心节点变为父节点（原来的轴心节点所在路径少了一个黑色节点，所以将兄弟变为红色，此时父节点的黑色路径是相同的了，但是父节点之上的路径少了一个黑色节点，所以将轴心节点变为父节点，继续调整）

情况三：兄弟是黑色，右侄子是黑色，左侄子是红色

将左侄子变为黑色，兄弟变为红色，此时右子树黑色高度降低，对兄弟节点继续右旋恢复高度，此时左侄子成为新的右兄弟

此时兄弟的右儿子是红色，符合情况4，按照情况4的方法继续调整

情况四：兄弟是黑色，右侄子是红色，左侄子是红色或黑色

将兄弟颜色改为和父节一样，右侄子和父节点都变为黑色

为了保证父节点变为黑色后高度不变需要将父节点左旋

x指向根节点，循环结束

为什么要将右侄子变为黑色：因为经过左旋后右侄子变为新的兄弟，代替了原来的兄弟，所以需要变为和兄弟颜色一样，也就是黑色

为什么要将兄弟变为和父节点一样：因为经过左旋后兄弟代替了父节点

为什么要将父节点变为黑色：因为父节点左旋弥补了被删除的黑色节点

此时路径恢复了

当前节点是父节点的右子树

和上面的情况一样，是镜像的

总结

会有两种情况导致循环退出不再需要调整：

情况二的时候轴心节点变为父节点，如果父节点是红色那么就可以退出将父节点改为黑色就可以恢复高度了

情况四：通过使用父节点弥补被删除节点恢复高度，最后再将轴心节点置为根节点退出循环

每一种情况都是尽可能向第四种情况靠近，实现兄弟是黑色，右侄子是红色的情况

代码

// 寻找x节点的最左节点
RbTreeNode* rbTree_mini(RbTree *T, RbTreeNode *x) {
    while (x->left != T->nil) {
        x = x->left;
    }
    return x;
}

// 寻找覆盖节点的右子树的最左节点
RbTreeNode* rbTree_successor(RbTree *T, RbTreeNode* x) {
    RbTreeNode *y = x->parent;

    // 寻找x节点的右子树的最左节点
    if (x->right != T->nil) {
        return rbTree_mini(T,x->right);
    }
}

void rbTree_delete_fixup(RbTree *T, RbTreeNode* x) {
    while ((x != T->root) && (x->color == BLACK)) {
        if (x == x->parent->left) {
            // w为兄弟节点
            RbTreeNode *w = x->parent->right;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                leftRotate(T,x->parent);
                w = x->parent->right;
            }
            if ((w->left->color == BLACK) && (w->right->color == BLACK)) {
                w->color = RED;
                x = x->parent;
            } else {
                if (w->right->color == BLACK) {
                    w->left->color = BLACK;
                    w->color = RED;
                    rightRotate(T,w);
                    w = x->parent->right;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->right->color = BLACK;
                leftRotate(T,x->parent);
                x = T->root;
            }
        } else {
            RbTreeNode *w = x->parent->left;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                rightRotate(T,x->parent);
                w = x->parent->left;
            }
            if ((w->left->color == BLACK) && (w->right->color == BLACK)) {
                w->color = RED;
                x = x->parent;
            } else {
                if (w->left->color == BLACK) {
                    w->right->color = BLACK;
                    w->color = RED;
                    leftRotate(T,w);
                    w = x->parent->left;
                }

                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->left->color = BLACK;
                rightRotate(T,x->parent);

                x = T->root;
            }
        }
    }
    x->color = BLACK;
}

// 删除节点
RbTreeNode* rbTreeDelete(RbTree *T, RbTreeNode *z) {
    // z是被覆盖的节点 y是删除节点 x是轴心节点负责旋转
    RbTreeNode *y = T->nil;
    RbTreeNode *x = T->nil;

    // 此时如果没有子树或只有一颗子树 那么就是要被删除的节点
    if ((z->left == T->nil) || (z->right == T->nil)) {
        y = z;
    } else {
        // 寻找删除节点 也就是覆盖节点的右子树的最左节点
        y = rbTree_successor(T,z);
    }

    // 找轴心节点 一般是被删除节点的左子节点
    if (y->left != T->nil) {
        x = y->left;
    } else if (y->right != T->nil) {
        x = y->right;
    }

    x->parent = y->parent;
    if (y->parent == T->nil) {
        // 如果y是根节点 那么x就成为新的根节点
        T->root = x;
    } else if (y == y->parent->left) {
        y->parent->left = x;
    } else {
        y->parent->right = x;
    }

    // 覆盖节点
    if (y != z) {
        z->key = y->key;
        z->value = y->value;
    }

    // 如果删除节点是黑色节点则需要调整
    if (y->color == BLACK) {
        rbTree_delete_fixup(T,x);
    }

    return y;
}

时间复杂度

就插入节点导致树失衡的情况，AVL和RB-Tree都是最多两次树旋转来实现复衡，旋转的量级是O(1)

删除节点导致失衡，AVL需要维护从被删除节点到根节点root这条路径上所有节点的平衡，旋转的量级为O(logN)，而RB-Tree最多只需要旋转3次实现复衡，只需O(1)，所以说RB-Tree删除节点的rebalance的效率更高，开销更小！

但是红黑树是通过改变节点颜色来避免旋转，具体开销还是要看改变颜色开销小还是改变指针开销小

B树与B+树

B树

性质

一颗M阶B树T满足一下条件：

每个结点最多拥有M棵子树
根结点至少拥有两棵子树
除了根节点以外，其余每个分支节点至少拥有M/2棵子树（保证树的平衡）
所有的叶子节点都在同一层
有k棵子树的分支节点则存在k-1个关键字，关键字按照递增顺序进行排序
关键字数量满足ceil(M/2)-1 <= n <= M-1

查找

首先从根节点开始查找，比较根节点中的关键字，如果比关键字大就在关键字的右边子节点查找，否则向左边子节点查找

比如查找P，判断出M比P小所以向右边的子树查出，读取QT的那一颗树，判断出比Q小，所以在QT树的最左边子树查找得到NP，在NP中查找到P关键字

插入

比如上图中的树是一颗5阶树，首先查找可以存放的位置，如果可以存放就直接存放，否则需要进行叶子节点的分裂

首先插入3、8、31、11：此时节点已经有四个关键字了，所以后面要继续插入的时候需要进行页的分裂，页的分裂就是将中间节点作为左右节点的父节点

插入23、29：

插入50、28、53：

删除

当关键字小于m/2时就需要进行节点的合并：

相邻两颗子树都是M/2-1则合并
左边子树大于m/2-1则向左边子树借
右边子树大于m/2-1则向右边子树借

删除A节点：

由于CF只有两个节点所以需要借节点，向右边的子树借一个节点，也就是将L变为根节点，I节点给CF子树

AB、DE子树只有两个节点，所以进行合并：

将A节点删除：

总结

B树相比于平衡二叉树在节点空间利用率上做了改进，一个节点能够容纳更多的数据，从而减少树的高度，减少查询的速度，很适合于磁盘上数据的存储

多叉树和B树之间的区别：

多叉树没有约束平衡
多叉树没有约束每个节点子树的数量
B树数据是按顺序排列的

B+树

查询

和B树大体相似，但是B+树所有的数据存放在叶子节点中，所以需要从根节点开始向下查找直到到达叶子节点

插入

插入全部在叶子节点上进行，按照关键字大小顺序排列

当叶子节点中关键字数量超过限制时需要进行节点的分裂

阶数限制为3：

插入95：插入关键字所在结点 [85、91、97] 包含 3 个关键字，等于阶数 M ，则将 [85、91、97] 分裂为两个结点 [85、91] 和结点 [97] , 关键字 95 插入到结点 [95、97] 中，并将关键字 91 上移至其双亲结点中，发现其双亲结点 [72、97] 中包含的关键字的个数 2 小于阶数 M ，插入操作完成

删除

在叶子节点删给删除，如果不会破坏规则则直接删除
如果删除的是父节点中的最大或最小关键字会涉及到更改双亲结点一直到根节点中所有关键字的修改：

删除整颗 B+树中最大的关键字 97 为例，查找并删除关键字 97 ，然后向上回溯，将所有关键字 97 替换为次最大的关键字 91

删除节点后如果导致节点关键字数量小于[M/2]：
- 如果兄弟节点可以借则向兄弟节点借
- 如果没有则和兄弟节点合并

删除51：向[21,37,44]的兄弟节点借，同时修改双亲结点中的关键字

删除59：发现该结点的兄弟结点 [21、37] 包含的关键字的个数 2 等于 ⌈M/2⌉，所以删除关键字 59 ，并将结点 [21、37] 和 [44] 进行合并 [21、37、44] ，然后向上回溯，将所有关键字 59 替换为次最大的关键字 44

总结

B+树是B树的基础上进行了改进，区别是：

B+树的高度比B树低，磁盘IO次数更少：B树的内部节点和叶子节点都保存了键值，导致每一个节点能够存放的记录数比较少，要保存相同的记录数就需要更多的节点，进而导致树高度的增加。B+树的非叶子节点只存放索引不存放数据，能够容纳更多的记录，因此B+树高度比B树低

B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳
B+树范围查询效率高：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便。但是B树需要通过中序遍历在父子节点之间来回跳转
B+树的插入和删除效率更高：B+树有大量冗余的节点，使得B+树在删除和插入时效率比较高，很少涉及树的变形

B*树

在B+树的构建过程中，为了保持树的平衡，节点的合并拆分是比较耗费时间的，所以B树就是在*如何减少构建中节点合并和拆分的次数，从而提升树的数据插入、删除性能

区别：

关键字个数上：B+树初始化的关键字初始化个数是cei(m/2)，b*树的初始化个数为（cei(2/3 *m)）
B+树节点满时就会分裂，而B*树节点满时会检查兄弟节点是否满（因为每个节点都有指向兄弟的指针），如果兄弟节点未满则向兄弟节点转移关键字，如果兄弟节点已满，则从当前节点和兄弟节点各拿出1/3的数据创建一个新的节点出来
B*树在内部节点和叶子节点都增加了指向兄弟节点的指针

Trie字典树

性质

根节点不包含字符，除根节点外每个节点都只包含一个字符
从根节点到任意节点，路径上经过的字符连接起来，为该节点对应的字符串
每个节点的所有子节点包含的字符都不相同

性能分析

搜索时间复杂度O(m)，m为字符串的长度

补充

应用场景：串的快速检索、串排序、前缀搜索

核心：利用字符串的公共前缀减少查询时间

跳表

在原来有序链表的基础上增加了多级索引，通过索引快速查找

性质

由许多层链表组成
每一层都是有序的链表
最底层Level 1的链表包含所有元素
如果一个元素出现在Level i的链表中，则在Level i之下的链表都会出现
每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下一层的元素

操作

搜索：从最上层元素开始搜索，找到就直接返回；找不到就根据该层元素向下一层查找

删除：在各个层中找到包含目标数的节点将其删除

插入

插入元素的时候元素所占有的层数是随机的，由随机算法产生
- 类似抛硬币，K满足p=1/2的正太分布，实现上一层元素的数量是下一层的一半，实现二分查找，类似
  比如得到K=2，那么1,2层都会插入该元素
先确定元素要占据的层数K，在Level1~K的各个层都插入数据

性能分析

O(logN)

和红黑树对比

实现简单
跳跃表的增加、删除操作只会改动局部，不像红黑树的增加、删除操作，因为需要节点重新着色和旋转，可能整棵树都要进行调整，因此在并发环境下，跳跃表加锁的粒度会更小一些，并发能力更强
因为跳跃表的每一层都是一个有序的链表，因此范围查找非常方便，优于红黑树的范围搜索的

跳跃表相比于红黑树，是用空间换时间（level 2层开始每一层都有会存储重复的数据），因此占用的内存空间比红黑树大

倒排索引

全文检索：在大量文档中找到包含某个单词出现的位置

like %单词%
- 无法使用数据库的索引
- 搜索效果差，无法实现复杂的搜索需求

正排索引：以文档对象的唯一ID为索引，以文档内容为记录

倒排索引：将文档内容中的单词作为索引，将包含该词的文档ID作为记录

过程

通过正排索引为每个文档赋予唯一的ID标识
生成倒排索引
- 对文档内容分为多个单词
- 按照单词作为索引，对应的文档id作为记录（链表）
查找
- 将查找内容分词通过倒排索引找到文档id，再对文档id取交集

哈夫曼树 & 哈夫曼编码

哈夫曼树又称为最佳判定树、最优二叉树，是一种带权路径长度最短的二叉树，常用于数据压缩。所谓树的带权路径长度，就是树中所有的叶子节点的权值乘以其到根节点的路径长度

哈夫曼编码

目的：为给定的字符集合构建二进制编码，使得编码的期望长度达到最短

哈夫曼编码不同于ASCII和Unicode这些字符编码，这些字符集中的码长都采用的是长度相同的编码方案，而哈夫曼编码使用的是变长编码，而且哈夫曼编码满足立刻可解码性（就是说任一字符的编码都不会是另一个更长字符编码的前缀），这样当一个字符的编码中的位被接收时，可以立即进行解码而无须等待之后的位来决定是否存在另一个合法的更长的编码