- 1. 二叉搜索树
- 特点
1） 任意节点左子树不为空,则左子树的值均小于根节点的值.
2） 任意节点右子树不为空,则右子树的值均大于于根节点的值.
3） 任意节点的左右子树也分别是二叉查找数
4） 没有键值相等的节点. - 二叉查找树的局限
二叉查找树在查找数据时，时间复杂度最好情况是O(logn) ，最坏情况下（退化为线性表时）时间复杂度O(n)。
* 2. B树
B树又名平衡多路查找树（查找路径不只两个），不同于常见的二叉树，它是一种多叉树，我们常见的使用场景一般是在数据库索引技术里，大量使用者B树和B+树的数据结构。
B树大多用在磁盘上用于查找磁盘的地址。因为磁盘会有大量的数据，有可能没有办法一次将需要的所有数据加入到内存中，所以只能逐一加载磁盘页，每个磁盘页就对应一个节点，而对于B树来说，B树很好的将树的高度降低了，这样就会减少IO查询次数，虽然一次加载到内存的数据变多了，但速度绝对快于AVL或是红黑树的。
搜索B树时，很明显，访问节点（即读取磁盘）的次数与树的高度呈正比，而B树与红黑树和普通的二叉查找树相比，虽然高度都是对数数量级，但是显然B树中log函数的底可以比2更大，因此，和二叉树相比，极大地减少了磁盘读取的次数。
B+树
B+树时B树的一种升级版本，B+树查找的效率要比B树更高、更稳定。
B+树是应文件系统所需而产生的一种B树的变形树(文件的目录一级一级索引,只有最底层的叶子节点(文件)保存数据.),非叶子节点只保存索引,不保存实际的数据,数据都保存在叶子节点中.B+树与B树的比较
1、B+树的层级更少：相较于B树，B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；
2、B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;
3、B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
4、B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。B树相对于B+树的优点：
如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。B+树相对于B树的最主要的优点：
- B+树只有叶子节点存放数据，而其他节点只存放索引，而B树每个节点都有Data域。所以相同大小的节点B+树包含的索引比B树的索引更多（因为B树每个节点还有Data域）
- B+树的叶子节点是通过链表连接的，所以找到下限后能很快进行区间查询，比B树中序遍历快
** 平衡二叉树**
平衡二叉树（Balanced Binary Tree）又被称为AVL树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。
AVL存在的局限性
由于维护这种高度平衡所付出的代价比从中获得的效率收益还大,故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树.当然,如果应用场景中对插入删除不频繁,只是对查找要求较高,那么AVL还是较优于红黑树.红黑树
概念
一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是red或black（非红即黑）。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍。它是一种弱平衡二叉树(由于是弱平衡，可以推出，相同的节点情况下，AVL树的高度低于红黑树)，相对于要求严格的AVL树来说，它的旋转次数少，所以对于搜索、插入、删除操作较多的情况下，我们就用红黑树。特点
1、每个节点非红即黑；
2、根节点是黑的；
3、每个叶节点(叶节点即树尾端NULL指针或NULL节点)都是黑的；
4、如果一个节点是红的,那么它的两儿子都是黑的；
5、对于任意节点而言，其到叶子点树NULL指针的每条路径都包含相同数目的黑节点；
6、高度始终保持在h = logn
7、红黑树的查找、插入、删除的时间复杂度最坏为O(logn)二叉搜索树、B树、B+树、AVL树、红黑树的常见面试题
B树和 B+树的区别
B/B+树用在磁盘文件组织、数据索引和数据库索引中。其中B+树比B 树更适合实际应用中操作系统的文件索引和数据库索引，因为：
1、B+树的磁盘读写代价更低
B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
2、B+树的查询效率更加稳定
由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
3、B树在元素遍历的时候效率较低
由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引。在数据库中基于范围的查询相对频繁，所以此时B+树优于B树。B树和红黑树的区别
最大的区别就是树的深度较高，在磁盘I/O方面的表现不如B树。
要获取磁盘上数据，必须先通过磁盘移动臂移动到数据所在的柱面，然后找到指定盘面，接着旋转盘面找到数据所在的磁道，最后对数据进行读写。磁盘IO代价主要花费在查找所需的柱面上，树的深度过大会造成磁盘IO频繁读写。根据磁盘查找存取的次数往往由树的高度所决定。
所以，在大规模数据存储的时候，红黑树往往出现由于树的深度过大而造成磁盘IO读写过于频繁，进而导致效率低下。在这方面，B树表现相对优异，B树可以有多个子女，从几十到上千，可以降低树的高度。AVL树和红黑树的区别
红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高。
1、红黑树和AVL树都能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。
2、由于设计，红黑树的任何不平衡都会在三次旋转之内解决。AVL树增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。
在查找方面：
红黑树的性质(最长路径长度不超过最短路径长度的2倍)，其查找代价基本维持在O(logN)左右，但在最差情况下(最长路径是最短路径的2倍少1)，比AVL要略逊色一点。
AVL是严格平衡的二叉查找树（平衡因子不超过1）。查找过程中不会出现最差情况的单支树。因此查找效率最好，最坏情况都是O(logN)数量级的。
所以，综上：
AVL比RBtree更加平衡，但是AVL的插入和删除会带来大量的旋转。 所以如果插入和删除比较多的情况，应该使用RBtree, 如果查询操作比较多，应该使用AVL。
“AVL是一种高度平衡的二叉树，维护这种高度平衡所付出的代价比从中获得的效率收益还大，故而实际的应用不多，更多的地方是用追求局部而不是非常严格整体平衡的红黑树。当然，如果场景中对插入删除不频繁，只是对查找特别有要求，AVL还是优于红黑的。”数据库为什么使用B树，而不使用AVL或者红黑树
我们假设B+树一个节点可以有100个关键字，那么3层的B树可以容纳大概1000000多个关键字（100+101100+101101*100）。而红黑树要存储这么多至少要20层。所以使用B树相对于红黑树和AVL可以减少IO操作mysql的Innodb引擎为什么采用的是B+树的索引方式
B+树只有叶子节点存放数据，而其他节点只存放索引，而B树每个节点都有Data域。所以相同大小的节点B+树包含的索引比B树的索引更多（因为B树每个节点还有Data域）
还有就是B+树的叶子节点是通过链表连接的，所以找到下限后能很快进行区间查询，比B树中序遍历快为什么B+树比B树更为友好
1、磁盘读写代价更低
树的非叶子结点里面没有数据，这样索引比较小，可以放在一个blcok（或者尽可能少的blcok）里面。避免了树形结构不断的向下查找，然后磁盘不停的寻道，读数据。这样的设计，可以降低io的次数。
2、查询效率更加稳定
非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
3、遍历所有的数据更方便
B+树只要遍历叶子节点就可以实现整棵树的遍历，而其他的树形结构 要中序遍历才可以访问所有的数据。为什么设计红黑树
红黑树通过它规则的设定，确保了插入和删除的最坏的时间复杂度是O(log N) 。
红黑树解决了AVL平衡二叉树的维护起来比较麻烦的问题，红黑树，读取略逊于AVL，维护强于AVL，每次插入和删除的平均旋转次数应该是远小于平衡树。
因此：
相对于要求严格的AVL树来说，红黑树的旋转次数少，所以对于插入、删除操作较多的情况下，我们就用红黑树。但是，只是对查找要求较高,那么AVL还是较优于红黑树.
京公网安备 11010502036488号