hash：容量固定（扩容性能下降）、hash算法避免冲突
二叉树
二叉平衡树和红黑树对比
红黑树旋转少
存储结构
数组顺序存储，满二叉树节省内存，非满二叉树浪费空间
顺序存储节点位置：节点X存储在数组中下标为i的位置，左子节点位置下标为2i，右子节点下标为2i+1
二叉平衡树 AVL
平衡是为了避免退化成链表（性能下降）
红黑树
增删改查时为维护严格平衡，调整数结构的代价较高，频繁增删改查维护平衡成本高
所以红黑树不要求绝对平衡，近似平衡即可
特性：黑根、叶节点(nil)黑色、节点的黑高相同、红色节点不相邻
应用场景
epoll存储文件描述符：红黑树+双向链表