10.2-3-4树
     10.1 特点
     10.2 查/增/删操作
         删：(1)非叶子节点(2)叶子节点1个元素(3)叶子节点2个/3个元素
         增：(1)目标节点有1个/2个元素    (2)目标节点有3个元素
     10.3 总结
11.B-树（B树）
     11.1 定义：
     11.2 用途：
     11.3 为什么数据库索引要用B树而不用二叉查找树？
12.B+树
     12.1 B+树与B-树的区别：
     12.2 B+树相比于B树的查询优势：
13.B*树
     13.1 介绍：
14 其他的树简介：
    14.1 R树：
    14.2 字典树(Trie树)：
    14.3 后缀树
15 总结

---

10.2-3-4树

    10.1 特点

        1. 每个节点最多有四个子节点和三个数据项
        2. 子节点个数 = 数据项个数 + 1       

    10.2 查/增/删操作

        搜索：2-3-4树的搜索其实和二叉搜索树非常相似，说到底它是一颗搜索树，节点还是按照从左到右依次增大的顺序排列的，对于给定的一个搜索值，从根节点出发，挨个比较，向下寻找就可以了。

        新增：1.通过搜索找到要插入的节点
                   2.如果目标节点只有1个/2个元素，直接插入即可
                   3.如果目标节点有3个元素，分裂该节点（比如下图的7，8，9。）
                   4.把分裂形成的根节点中的 key 看成向上层插入的 key （将8插入到上层节点中）
                   5. 循环执行2，3，4

        删除：

            情况1：如果目标是非叶子节点，将后继节点与待删除节点位置互换。

            情况2：如果目标是叶子节点且有2个/3个元素，直接删除即可

            情况3：如果目标节点是叶子节点且只有1个元素。
            处理方法1：父节点下移与子节点合并
            处理方法2：父节点下移成单独一个子节点，然后2个key的子节点上移一个key与父节点合并。

父节点下移与子节点合并 父节点下移，子节点上移

    10.3 总结

        2-3-4 树是红⿊树的⼀种等同，这意味着它们是等价的数据结构。换句话说，对于每个 2-3-4 树，都存在着⾄少⼀个数据元素是相同次序的红⿊树。在 2-3-4 树上的插⼊和删除操作也等价于在红⿊树中的颜⾊翻转和旋转。这使得它成为理解红⿊树背后的逻辑的重要⼯具。

11.B-树（B树）

    11.1 定义：

        B树是⼀种多路搜索树，要注意，并不是⼆叉树。一棵 m 阶的 B 树具有如下特性：（阶:最多子节点数目）

        1、根节点至少有两个孩子。
        2、每个中间节点都包含 k - 1 个元素和 k 个孩子，其中 m/2 <= k <= m。
        3、每一个叶子节点都包含 k - 1 个元素，其中 m/2 <= k <= m。
        4、所有的叶子节点都位于同一侧。
        5、每个节点中的元素从小到大排列，节点当中的 k - 1 个元素正好是 k 个孩子包含的元素的值域划分。

    11.2 用途：

        B-树主要应⽤在⽂件系统。是为了将⼤型数据库⽂件存储在硬盘上并减少访问硬盘次数的⼀种平衡多路查找树。

    11.3 为什么文件索引要用B树而不用二叉查找树？

        如下图所示：我们从1-20中查找数字9

        二者对比我们发现：
        1. B-树在内存中比较了4次（10，3，7，9）
            二叉查找树也比较了4次（10，6，7，9）
        2. 但是当我们加载磁盘数据到内存的时候，是以 数据页 为单位进行加载。不同节点的内容很有可能在不同数据页上。我们再看上图，B-树中只需要进行3次磁盘I/O（3,7算一次）,而二叉查找树还是需要4次
        总结：内存中的运算时间可以忽略不计，B-树主要减少了磁盘I/O

12.B+树

    12.1 B+树与B-树的区别：

        b+树，是b树的一种变体，查询性能更好。m阶的b+树的特征如下：

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

    12.2 B+树相比于B树的查询优势：

        1. b+树的中间节点不保存数据，所以磁盘页能容纳更多节点元素，空间使⽤率更⾼；
        2. b+树查询必须查找到叶子节点，b树只要匹配到即可不用管元素位置，因此b+树查找更稳定（并不慢）；
        3. 对于范围查找来说，b+树只需遍历叶子节点链表即可，b树却需要重复地中序遍历

13.B*树

    13.1 介绍：    

        B*tree是B+tree的变体，在B+树的基础上给非根和非叶子结点再增加指向兄弟的指针

14 其他的树简介：

    14.1 R树：

        R树就很好的解决了⾼维空间搜索问题（例如：查找20英⾥以内所有的餐厅）。它把B树的思想很好的扩展到了多维空间，采⽤了B树分割空间的思想，并在添加、删除操作时采⽤合并、分解结点的⽅法，保证树的平衡性。因此，R树就是⼀棵⽤来存储高维数据的平衡树。

面积最大的矩形在R树的最上层

    14.2 字典树(Trie树)：

        Trie树，是哈希树的一种变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。  

    14.3 后缀树

        将字符串XMADAMYX的所有后缀拼成一个字典树。如下图所示       

        常用于：(1)查找字符串o是否在字符串S中
                      (2)指定字符串T在字符串S中的重复次数
                      (3)字符串S中的最长重复子串  

15 总结：

    1. ⼆叉搜索树：⼆叉树，每个结点只存储⼀个关键字，等于则命中，⼩于⾛左结点，⼤于⾛右结点；
    2. B-树：多路搜索树，每个结点存储M/2到M个关键字，⾮叶⼦结点存储指向关键字范围的⼦结点；
    3. 所有关键字在整颗树中出现，且只出现⼀次，⾮叶⼦结点可以命中；
    4. B+树：在B-树基础上，为叶⼦结点增加链表指针，所有关键字都在叶⼦结点中出现，⾮叶⼦结点作为叶⼦结点的索引；B+树总是到叶⼦结点才命中；
    5. B*树：在B+树基础上，为⾮叶⼦结点也增加链表指针，将结点的最低利⽤率从1/2提⾼到2/3；