1.二叉查找树

• 左子树上所有结点的值均小于或等于它的根结点的值。
• 右子树上所有结点的值均大于或等于它的根结点的值。
• 左、右子树也分别为二叉排序树。

普通的二叉查找树在极端情况下可退化成链表，此时的增删查效率都会比较低下。为了避免这种情况，就出现了一些自平衡的查找树，比如 AVL，红黑树等。这些自平衡的查找树通过定义一些性质，将任意节点的左右子树高度差控制在规定范围内，以达到平衡状态。

2.AVL树
AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(logn)。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。AVL树得名于它的发明者G. M. Adelson-Velsky和Evgenii Landis，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。

节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。

左旋，右旋

3.红黑树

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

最后两条，可以保证任意节点到其每个叶子节点路径最长不会超过最短路径的2倍。

当某条路径最短时，这条路径必然都是由黑色节点构成。当某条路径长度最长时，这条路径必然是由红色和黑色节点相间构成（性质4限定了不能出现两个连续的红色节点）。而性质5又限定了从任一节点到其每个叶子节点的所有路径必须包含相同数量的黑色节点。

此时，在路径最长的情况下，路径上红色节点数量 = 黑色节点数量。该路径长度为两倍黑色节点数量，也就是最短路径长度的2倍。

• 新插入的节点为红色，如果叔叔节点为红色，父亲节点和叔叔节点直接变色即可
• 如果叔叔节点为黑色，则需要先左旋或者右旋，再交换颜色。

4. 跳表

• 链表不适用于二分查找。在原始链表的基础上，我们增加了一个索引链表。原始链表的每两个结点，有一个结点也在索引链表当中。同时增加多层索引可以进一步提升查询效率

  
  
  image.png
• 插入操作
  随着原始链表的新结点越来越多，索引会渐渐变得不够用了，因此索引结点也需要相应作出调整。
  如何调整索引呢？我们让新插入的结点随机“晋升”，也就是成为索引结点。新结点晋升成功的几率是50%。
  假设第一次随机的结果是晋升成功，那么我们把结点10作为索引结点，插入到第1层索引的对应位置，并且向下指向原始链表的结点10：
  新结点在成功晋升之后，仍然有机会继续向上一层索引晋升。我们再进行一次随机，假设随机的结果是晋升失败，那么插入操作就告一段落了。
• 删除操作
  删除节点，并将索引中的对应节点也删除

5. B树
   数据库索引是存储在磁盘上的，利用索引查询时，逐一加载每一个磁盘页，磁盘页对应着索引树的节点。为了减少磁盘IO次数，将树变得矮胖。
   B树（balance tree）是一种多路平衡查找树，它的每一个节点最多包含k个孩子，k被称为B树的阶。k的大小取决于磁盘页的大小。

• 根结点至少有两个子女。
• 每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m
• 每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m
• 所有的叶子结点都位于同一层

• 每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划

  
  
  image.png

6. B+树

• 有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
• 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
  即每一个叶子节点都带有指向下一个节点的指针，形成了一个有序链表。

• 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

  
  
  image.png
• 在数据库的聚集索引（clustered Index）中，叶子节点直接包含卫星数据。在非聚集索引（NonClustered Index）中，叶子节点带有指向卫星数据的指针。
• 查询数据时，B+树的中间节点没有卫星数据，所以同样大小的磁盘页可以容纳更多的节点元素。这就意味着，数据量相同的情况下，B+树的结构比B树更加矮胖，因此查询时IO次数也更少
• B+树的查询必须最终查询到叶子节点，而B树只要找到匹配元素即可，无论匹配元素处于中间节点还是叶子节点，因此，B树的查找性能并不稳定（最好情况是只查根节点，最坏情况是查到叶子节点）。而B+树的每一次查找都是稳定的。
• 范围查询
  只需要在链表上做遍历