数据结构

STL中的堆 优先级队列的底层算法

二叉排序树

二叉树是指任何节点最多只允许两个子节点的树。两个子节点称为左子节点和右子节点。
二叉排序树提供对数时间的元素插入和访问,二叉排序树的节点放置规则:任何检点的键值一定大于其左子树的每个节点的键值,并小于其右子树的每一个节点的键值。因此,从根节点一直向左走,直至左路可走,即得最小元素;从根节点一直向右走,直至无右路可走,即得最大元素。

二叉排序树的搜索时间复杂度为$O(log_2n)$到$O(n)$

AVL树

AVL树是”加上额外平衡条件”的二叉搜索树。平衡条件的建立是为了确保整棵树的深度为$O(logN)$。AVL-tree要求任何节点的左右子树高度相差最多1。
AVL树的搜索时间复杂度为$O(log_2n)$

红黑树

RB-tree不仅是二叉搜索树,而且必须满足以下规则:

  1. 每个节点不是红色就是黑色。
  2. 根节点为黑色。
  3. 如果节点为红色,其子节点必须为黑色。
  4. 任一节点到NULL(树尾端)的任何路径,所含黑节点数目必须相同。

红黑树的搜索时间复杂度为$O(log_2n)$
STL中的红黑树是map、set、multiset、multimap的底层
epoll底层内核事件表对文件描述符的管理使用红黑树

B树(B-树)

一个m阶的B树具有如下几个特征:

  1. 根结点至少有两个子女。
  2. 每个中间节点都包含k-1个元素和k个孩子,其中 $m/2 \le k \le m$
  3. 每一个叶子节点都包含k-1个元素,其中 $m/2 \le k \le m$
  4. 所有的叶子结点都位于同一层。
  5. 每个节点中的元素从小到大排列,节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

B+树

一个m阶的B+树具有如下几个特征:

  1. 有k个子树的中间节点包含有k个元素(B树中是k-1个元素),每个元素不保存数据,只用来索引,所有数据都保存在叶子节点。
  2. 所有的叶子结点中包含了全部元素的信息,及指向含这些元素记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。
  3. 所有的中间节点元素都同时存在于子节点,在子节点元素中是最大(或最小)元素

MySQL索引就是使用B+树
B+树相比B树的优势:

  1. I/O次数更少(单一节点存储更多元素)
  2. 查找性能更稳定(搜索查找都要查找到叶子节点)
  3. 范围查找简便(所有叶子节点形成有序链表)

B*树

哈希表

哈希表查找、插入、删除只需要接近$O(1)$的时间复杂度.
SGI STL提供的hashset、hashmap、hashmultiset、hashmultimap使用的底层结构即为哈希表
缺点:

  1. 哈希表基于数组,创建后扩展困难,hash表表基本填满时,性能下降严重.
  2. 一个关键字可能对应多个散列地址
  3. 需要范围查找时,效果不好

跳表

跳表具有如下性质:

  1. 由很多层结构组成
  2. 每一层都是一个有序的链表
  3. 最底层(Level 1)的链表包含所有元素
  4. 如果一个元素出现在 Level i 的链表中,则它在 Level i 之下的链表也都会出现。
  5. 每个节点包含两个指针,一个指向同一链表中的下一个元素,一个指向下面一层的元素

跳表的搜索时间复杂度为$O(log_2n)$到$O(n)$,其搜索时间复杂度大部分情况下与红黑树相当,但实现难度比红黑树低

1
2
3
4
5
6
7
         Top
|
Level 3 2----------->21------->37------------------>
| | |
Level 2 2-->7------->21------->37-->71------------->
| | | | |
Level l 2-->7-->14-->21-->32-->37-->71-->85-->117-->

Redis底层使用跳表

倒排表

参考资料