1、平衡二叉排序树 

　   二叉查找树定义：又称为是二叉排序树（Binary Sort Tree）或二叉搜索树。二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

　　1) 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

　　2) 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；

　　3) 左、右子树也分别为二叉排序树；

　　4) 没有键值相等的节点。

      平衡二叉树定义：平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用算法有红黑树、AVL树等。在平衡二叉搜索树中，我们可以看到，其高度一般都良好地维持在O(log2n)，大大降低了操作的时间复杂度。

       平衡二叉排序树兼具平衡二叉树与二叉排序树的特性。

2、AVL树

        AVL树是最先发明的自平衡二叉排序树。查找、插入和删除在平均和最坏情况下都是O(logn)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉排序树来说，时间上稳定了很多。

       红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。

红黑树的性质：

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

　　性质1. 节点是红色或黑色。

　　性质2. 根是黑色。

　　性质3. 所有叶子都是黑色（叶子是NIL节点）。

　　性质4. 每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)

　　性质5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

        这些约束确保了红黑树的关键特性: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

3、红黑树与AVL树的区别

红黑树的高度问题
        棵拥有n个内部结点的红黑树的树高h<=2log(n+1)

红黑树的优点
         红黑是用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决，而AVL是严格平衡树，因此在增加或者删除节点的时候，根据不同情况，旋转的次数比红黑树要多。所以红黑树的插入效率更高！！！

与AVL树的比较
        红黑树要求从根节点到叶子节点的最长路径不大于最短路径的两倍
         AVL 树要求每一个子树的左右孩子节点高度差不超过1
         保持平衡的要求上面，AVL树要求大于RBtree, 也就带来了search, insert 和delete操作的性能差异

相同点
        插入、删除操作为了保持原来的性质，有可能要进行必要的调整，主要看调整的代价，时间复杂度；其中AVL树的调整频繁，代价大(要保持高度平衡)，而RBtree 删除和插入的时间复杂度要好于AVL，
而对于search 操作而言，不涉及旋转调整操作，由于AVL树保持高度平衡，树的最大高度不超过1.44log(n), 而红黑树最大深度不超过 2log(n+2),
使用红黑树为何能比AVL树高效的原因
      从1这点来看红黑树是牺牲了严格的高度平衡的优越条件为代价红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。
        此外，由于它的设计，任何不平衡都会在三次旋转之内解决。
        红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。
        所以红黑树的插入效率更高

主要是维持原有性质需要进行旋转的次数和时间复杂度

分析
如果插入一个node引起了不满足树的性质，比如改变了红黑树的性质，或者破坏了AVL树的平衡性质，AVL和RB-Tree 都是最多只需要两次2次旋转操作，即两者都是O(1), 但在删除节点的时候，最坏情况下，AVL树需要维护从被删除NODE到root 这条路径上面所有NODE的平衡性，因此平衡性为O(logN), 而RB-Tree 做多只需要三次旋转，只需要0(1) 的复杂度。

其次，AVL的结构相对于RB-TREE来说更为平衡，在插入和删除的时候更加容易引起树的unbalanace，因此在大量数据需要插入或者删除时，AVL需要rebalance的频率会更高。因此，RB-Tree在需要大量插入和删除node的场景下，效率更高。自然，由于AVL高度平衡，因此AVL的search效率更高。

红黑树的应用领域
java 集合类和c ++ STL
典型的应用是关联数组，ava中的TreeSet,TreeMap，广泛用在C++的STL中。如map和set都是用红黑树实现的

Linux
进程调度中的完全公平调度算法，在左边的节点最需要CPU,实现了选择哪一个进程获得CPU进行运行（比如上图中的1节点，1数值代表进程的虚拟时钟vruntime。）
内存管理模块
在这里补充下vruntime

CFS调度器设计了一个参数叫Virtual Runtime（简称vruntime）来记录当前任务(进程)所获得的CPU运行时间，值越小代表获得的CPU运行时间也少，不符合公平的原则，因此该节点就是进程调用器应该选择获得CPU运行时间的进程

选择RBTree 还是 AVL
简单来说，就是看你对这个数据结构的使用要求，如果

应用操作性能主要集中在查询search操作的话，那就应该选择AVL
应用操作性能主要集中delete和insert 的话还是选择RBTree更加具有优势
每个进程的累计运行时间保存在自己的vruntime字段里，哪个进程的vruntime最小就获得本轮运行的权利。

很多数据结构都采用了 链表+ 红黑树

Java 中的Hashmap
epoll I/O服用模型中的监控文件就绪文件描述符
linux CFS

4、B树 

　B树也是一种用于查找的平衡树，但是它不是二叉树。

　　B树的定义：B树（B-tree）是一种树状数据结构，能够用来存储排序后的数据。这种数据结构能够让查找数据、循序存取、插入数据及删除的动作，都在对数时间内完成。B树，概括来说是一个一般化的二叉查找树，可以拥有多于2个子节点。与自平衡二叉查找树不同，B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。这种数据结构常被应用在数据库和文件系统的实作上。

在B树中查找给定关键字的方法是，首先把根结点取来，在根结点所包含的关键字K1,…,Kn查找给定的关键字（可用顺序查找或二分查找法），若找到等于给定值的关键字，则查找成功；否则，一定可以确定要查找的关键字在Ki与Ki+1之间，Pi为指向子树根节点的指针，此时取指针Pi所指的结点继续查找，直至找到，或指针Pi为空时查找失败。

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

　　1) 定义任意非叶子结点最多只有M个儿子；且M>2；

　　2) 根结点的儿子数为[2, M]；

　　3) 除根结点以外的非叶子结点的儿子数为[M/2, M]；

　　4) 每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）

　　5) 非叶子结点的关键字个数=指向儿子的指针个数-1；

　　6) 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；

　　7) 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；

　　8) 所有叶子结点位于同一层；

       如下图为一个M=3的B树示例：

　　B树创建的示意图：

 

 

5. B+树

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

　　1) 其定义基本与B-树相同，除了：

　　2) 非叶子结点的子树指针与关键字个数相同；

　　3) 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；

　　4) 为所有叶子结点增加一个链指针；

　　5) 所有关键字都在叶子结点出现；

　　下图为M=3的B+树的示意图：

　　B+树的搜索与B树也基本相同，区别是B+树只有达到叶子结点才命中（B树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

　　B+的性质：

　　1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；

　　2.不可能在非叶子结点命中；

　　3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；

　　4.更适合文件索引系统。

　　下面为一个B+树创建的示意图：

 

6. B*树

　　B*树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针，将结点的最低利用率从1/2提高到2/3。

　　B*树如下图所示：

　　B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）；

　　B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；

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

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

 

7. Trie树

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

　　Tire树的三个基本性质：

　　1) 根节点不包含字符，除根节点外每一个节点都只包含一个字符；

　　2) 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串；

　　3) 每个节点的所有子节点包含的字符都不相同。

　　Tire树的应用：

　　1) 串的快速检索

　　给出N个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。

在这道题中，我们可以用数组枚举，用哈希，用字典树，先把熟词建一棵树，然后读入文章进行比较，这种方法效率是比较高的。

　　2) “串”排序

　　给定N个互不相同的仅由一个单词构成的英文名，让你将他们按字典序从小到大输出。用字典树进行排序，采用数组的方式创建字典树，这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可。

　　3) 最长公共前缀

　　对所有串建立字典树，对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数，于是，问题就转化为求公共祖先的问题。

myaql索引实现B+树：

b 树的查找过程:
      如图所示，如果要查找数据项 29，那么首先会把磁盘块 1 由磁盘加载到内存， 此时发生一次 IO，在内存中用二分查找确定 29 在 17 和 35 之间，锁定磁盘块 1 的 P2 指针，内存时间因为非常短(相比磁盘的 IO)可以忽略不计，通过磁盘块 1 的 P2 指 针的磁盘地址把磁盘块 3 由磁盘加载到内存，发生第二次 IO，29 在 26 和 30 之间， 锁定磁盘块 3 的 P2 指针，通过指针加载磁盘块 8 到内存，发生第三次 IO，同时内存 中做二分查找找到 29，结束查询，总计三次 IO。真实的情况是，3 层的 b+树可以表 示上百万的数据，如果上百万的数据查找只需要三次 IO，性能提高将是巨大的，如果 没有索引，每个数据项都要发生一次 IO，那么总共需要百万次的 IO，显然成本非常非 常高。

注意:当 b+树的数据项是复合的数据结构(建立的是复合索引)，比如 (name,age,sex)的时候，b+树是按照从左到右的顺序来建立搜索树的，比如当(张 三,20,F)这样的数据来检索的时候，b+树会优先比较 name 来确定下一步的搜索方向， 如果 name 相同再依次比较 age 和 sex，最后得到检索的数据;但当(20,F)这样的没 有 name 的数据来的时候，b+树就不知道下一步该查哪个节点，因为建立搜索树的时 候 name 就是第一个比较因子，必须要先根据 name 来搜索才能知道下一步去哪里查 询。比如当(张三,F)这样的数据来检索时，b+树可以用 name 来指定搜索方向，但下 一个字段 age 的缺失，所以只能把名字等于张三的数据都找到，然后再匹配性别是 F 的数据了， 这个是非常重要的性质，即索引的最左匹配特性。注意:B+tree 多列索 引保存的顺序是按照索引创建的顺序，检索索引时按照此顺序检索。

最左前缀原则中 where 字句有 or 出现还是会遍历全表。

为什么使用B+树作为mysql的索引结构为什么不用红黑树和二叉树？

    数据库文件很大，需要存储到磁盘上，索引的结构组织要尽量减少查找过程中磁盘 I/O 的存取次数。

   1、高度原因

       B+树中的每个结点可以包含大量的关键字，这样树的深度降低了，所以任何关键 字的查找必须走一条从根结点到叶子结点的路，所有关键字查询的路径长度相同，导致 每一个数据的查询效率相当，这就意味着查找一个元素只要很少结点从外存磁盘中读入 内存，很快访问到要查找的数据，减少了磁盘 I/O 的存取次数。

   2.磁盘预读原理和局部性原理

        将一个节点的大小设为等于一个页，这样每个节点只需要一次 I/O 就可以完全载 入。