查找

顺序查找

按照顺序一个个比较,直到序列末尾

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时间轮

2022616155327

时间轮被划分为 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 的任务

分层时间轮

2022616155817

当上层的时间轮转完一圈时,下层的定时器就要增加一个刻度

假设我们的任务需要在每天的 7:30:20 秒执行一次。任务首先添加于小时级别时钟轮的第 7 号刻度上,当其轮询线程访问到第 7 号刻度时,就将此任务转移到分钟级别时钟轮的第 30 号刻度上。当分钟级别的时钟轮线程访问到第 30 号刻度,就将此任务转移到秒级别时钟轮的第 20 号刻度上。当秒级别时钟轮线程访问到第 20 号刻度时,最终会将任务交给异步线程负责执行

bitmap

位图通过数组下标来定位数据,所以访问效率非常高

1存在 => 0100002存在 => 0010001,2都存在 => 011000

布隆过滤器

布隆过滤器

一串数据通过n个散列函数将一个位图的n位设置为1,当要查询时,对数据进行散列 判断对应的n位是否都为1 若都为1, 则就是可能存在

所以布隆过滤器也没有足够的信息可以删除指定的key,为了应对缓存数据过期,可以采用定期重建的方法,重建完保持两个过滤器的双写,一段时间后,就把全部请求都给到较新的这个过滤器上,清除老的过滤器

布谷鸟过滤器

2022817204730

哈希表的基本单位称为条目(entry)。 每个条目存储一个指纹(fingerprint),指纹指的是使用一个哈希函数生成的n位比特位

相比布隆过滤器,布谷鸟过滤器可以通过从哈希表删除相应的指纹删除插入的项,由于哈希的特性,是存在误删的可能的,同时,只要不发生桶溢出,在查询的时候就不会出现假阳

索引

功能性需求

非功能性需求

索引常用数据结构

  1. 散列表
  2. 红黑树
  3. B+树
  4. 跳表
  5. 布隆过滤器