队列
- FIFO原则
- 栈
集合
无重复元素， map key
链表、数组
List, array
字典、关联数组
map
树
二叉树
What: 每个节点的子节点小等于2 Why: 有序数组的优势在于二分查找（O(lgn)， 插入：O(n)），链表的优势在于插入和删除(O(1), O(n))， 折中的话会用到二叉树 https://juejin.im/post/5ab5a01d518825555c1d9a24
完全二叉树
What: 只有最后一层的节点不满，并且最后一层的节点都集中在改成最左边的若干位置的二叉树；按顺序一维数组存储 Why: 最大堆（父节点都比子节点大）和最小堆（父节点都比子节点小） 优先队列的实现（最大堆）。 N个节点的高度d=logn 建堆O(n) 插入和删除O(logn) http://wiki.jikexueyuan.com/project/easy-learn-algorithm/amazing-priority-array.html
二叉搜索树
- 左子树所有节点的值都小于根节点， 右子树所有节点的值都大于根节点的值
- 可升级为平衡二叉树(avl) 和 红黑树
平衡二叉树
- 二叉搜索树 & 左右子树的高度差不超过1， 插入和删除是若超过1， 则需要进行旋转，使其恢复平衡
- 查找和复杂度为O(logn)
红黑树
- 是一个平衡二叉树， 但不是完美平衡二叉树。 对数时间（logn）内查找、插入、删除
- 特征：每个节点要么红，要么黑； 根节点都是黑色； 红色节点的，子节点都是黑色；从任一节点到每个叶节点的包含的黑色节点的数目一样
- Map, set 底层都是红黑树实现
B、B+、B*树
- B树：多叉树，又名平衡多路查找树； 数据库的索引中应用广泛； 全局遍历需要中序遍历
- B+树：所有关键字都在叶子节点，叶子节点间从小到大链接， 所以扫库只要遍历叶子节点， 同样的范围查找也是方便。 由于树的层级少，所以查询的速度比B树快； 关键字都存储在叶子节点，所以查询速度更稳定。
- B树：增加了兄弟指针， B+树在一个节点满时，直接创建新的节点，而B则先看下个兄弟节点，没满则复制一部分到兄弟节点，所以空间利用率更高。
LSM树 （LOG STRUCT MERGE-TREES）
将大树分解成若干小树， 牺牲读的性能，提高写的性能。
bitset
大规模数据的排重和检查
