实验室项目介绍：
###DQEMU:
核心技术
难点:
ABA:
位图
用来查找海量数据。
32位无符号整数是需要 232bit，也就是 229B，4GB足够了。
如果数的范围超过了32位，那用布隆过滤器，简单的说就是把整数换成整数的哈希，可以排除这个数不存在的情况。
##哈希表的实现
哈希函数
尽量用加法和位运算实现。
冲突解决 开链法
哈希函数结果相同的用一个链表串起来。缺点，链太长影响查询速度。
哈希表扩容
开一个两倍大的空间然后执行一次resize。
平衡树和红黑树
平衡树(AVL):每个子树左右的高度差小于等于1.
红黑树
跳表
间隔 1 2 4 8 16 …
先查1->7->13然后依次往下查
空间复杂度O(n)
时间复杂度O(log n)
为什么数据库用B+树
哈希表不能范围查询。
平衡树和红黑树调整代价大。
B树比较平均但是B+树更好。
叶子节点用指针相联，适合范围查询。
只有叶子节点存数据，中间节点能够存储更多的索引，减少树高，减少读取磁盘的次数，适合磁盘存储。
倒排索引
单词：出现位置
