查找
顺序查找
按照顺序一个个比较，直到序列末尾
int seq_search(int array[], int n, int key){ int i; for(i = 0; i < n; i++) { if(key == array[i]) { return i; //查找成功 } } return -1; //查找失败}二分查找
通过对一个有序数组中对元素依次比较，从而能实现对数级别时间复杂度的查找
根据左右指针计算出一个mid指针 如果mid指针处的元素等于目标值 则要查找的目标就是在这里
否则如果mid处的指针比目标值大 则右指针等于mid-1 否则左指针等于mid+1
然后重复上述操作 直到左指针大于右指针
int l = 0, r = a.length - 1;while (l <= r) { int mid = l + (r - l) / 2; if (a[mid].equals(target)) { return mid; } if (less(target, a[mid])) {// 要查找的元素在左边 r = mid - 1; } else if (greater(target, a[mid])) { // 要查找的元素在右边 l = mid + 1; }}return -1;- 二分查找依赖于顺序表结构
- 二分查找针对有序数据
- 二分查找依赖于一整块内存的随机访问，对于过大无法在内存中分配空间的数据也不适合
这个算法在快速定位BUG的时候也挺好用，一分为二，确定问题在前端还是后端，再继续划分，确定问题在系统哪一层
时间轮
round时间轮
时间轮被划分为 8 个 slot，每个 slot 代表 1s，当前时针指向 2。假如现在需要调度一个 3s 后执行的任务，应该加入 2+3=5 的 slot 中；如果需要调度一个 12s 以后的任务，需要等待时针完整走完一圈 round 零 4 个 slot，需要放入第 (2+12)%8=6 个 slot
怎么区分每个任务是否需要立即执行，还是需要等待下一圈 round，甚至更久时间之后执行呢？所以我们需要把 round 信息保存在任务中。例如图中第 6 个 slot 的链表中包含 3 个任务，第一个任务 round=0，需要立即执行；第二个任务 round=1，需要等待 18=8s 后执行；第三个任务 round=2，需要等待 28=8s 后执行。所以当时针转动到对应 slot 时，只执行 round=0 的任务
分层时间轮
当上层的时间轮转完一圈时，下层的定时器就要增加一个刻度
假设我们的任务需要在每天的 7:30:20 秒执行一次。任务首先添加于小时级别时钟轮的第 7 号刻度上，当其轮询线程访问到第 7 号刻度时，就将此任务转移到分钟级别时钟轮的第 30 号刻度上。当分钟级别的时钟轮线程访问到第 30 号刻度，就将此任务转移到秒级别时钟轮的第 20 号刻度上。当秒级别时钟轮线程访问到第 20 号刻度时，最终会将任务交给异步线程负责执行
bitmap
位图通过数组下标来定位数据，所以访问效率非常高
1存在 => 0100002存在 => 0010001,2都存在 => 011000布隆过滤器
一串数据通过n个散列函数将一个位图的n位设置为1，当要查询时，对数据进行散列 判断对应的n位是否都为1 若都为1, 则就是可能存在
所以布隆过滤器也没有足够的信息可以删除指定的key，为了应对缓存数据过期，可以采用定期重建的方法，重建完保持两个过滤器的双写，一段时间后，就把全部请求都给到较新的这个过滤器上，清除老的过滤器
布谷鸟过滤器
- 布谷鸟哈希：使用两个哈希函数对一个key进行哈希，得到桶中的两个位置，如果有空位，key就放在空位里，否则就要随机踢掉一个元素，踢出的元素再计算哈希找到相应的存储位置
哈希表的基本单位称为条目（entry）。 每个条目存储一个指纹（fingerprint），指纹指的是使用一个哈希函数生成的n位比特位
相比布隆过滤器，布谷鸟过滤器可以通过从哈希表删除相应的指纹删除插入的项，由于哈希的特性，是存在误删的可能的，同时，只要不发生桶溢出，在查询的时候就不会出现假阳
索引
功能性需求
- 索引的数据是格式化数据还是非格式化数据
- 索引的数据是静态数据还是动态数据
- 索引存储在内存还是硬盘
- 单值查找还是区间查找
- 单条件查找还是多条件组合查找
非功能性需求
- 对存储空间的消耗不能过大
- 考虑索引查询效率的同时，还要考虑索引的维护成本
索引常用数据结构
- 散列表
- 红黑树
- B+树
- 跳表
- 布隆过滤器