Redis的实现五：二叉堆的数据结构和TTL、c，c++的实现

? ? ? ? 概述：Redis的主要用途是作为缓存服务器，管理缓存大小的一种方法是通过显式设置ttl(生存 时间)。ttl可以使用计时器来实现。不幸的是，上一章的计时器是固定值(使用链表);因 此，需要一种排序数据结构来实现任意可变的超时;而堆数据结构是一种流行的选择。 与我们之前使用的AVL树相比，堆数据结构的优势在于占用的空间更少。

? ? ? ?快速回顾一下堆数据结构:

? ? ? ?1. 堆是一个二叉树，被打包成一个数组;而树的布局是固定的。父子关系是隐式的， 指针不包含在堆元素中。

? ? ? 2. 这棵树上唯一的约束是父母不能比他们的孩子大。

? ? ? 3. 元素的值可以更新。如果值改变了: ?它的值比之前大:它可能比它的子元素大，如果是这样，就把它和最小的子 元素交换，这样亲子约束就再次得到满足。现在，其中一个孩子比以前大， 继续这个过程，直到达到一个休假。 ?它的值变小了:同样地，与它的父节点交换，直到到达根节点。? ?

? ? ?4. 新元素以叶子的形式添加到数组的末尾。如上所述保持约束。

? ? ?5. 当从堆中删除一个元素时，将其替换为数组中的最后一个元素，然后维护约束， 就好像它的值被更新了一样。

二叉堆的完整例子：

#include <stdio.h>

#define MAX_HEAP_SIZE 100

// 定义最小堆结构
struct MinHeap {
    int arr[MAX_HEAP_SIZE];
    int size;
};

// 函数声明
void initHeap(struct MinHeap* heap);
void insertElement(struct MinHeap* heap, int value);
void deleteMin(struct MinHeap* heap);
void printHeap(struct MinHeap* heap);

int main() {
    struct MinHeap heap;
    initHeap(&heap);

    // 添加元素
    insertElement(&heap, 5);
    insertElement(&heap, 3);
    insertElement(&heap, 8);
    insertElement(&heap, 1);

    // 打印堆
    printf("堆的元素：");
    printHeap(&heap);

    // 删除最小元素
    deleteMin(&heap);

    // 打印堆
    printf("删除最小元素后的堆：");
    printHeap(&heap);

    return 0;
}

// 初始化堆
void initHeap(struct MinHeap* heap) {
    heap->size = 0;
}

// 向堆中插入元素
void insertElement(struct MinHeap* heap, int value) {
    if (heap->size == MAX_HEAP_SIZE) {
        printf("堆已满\n");
        return;
    }

    // 将新元素添加到末尾
    heap->arr[heap->size] = value;
    heap->size++;

    // 上移操作，维护堆的性质
    int currentIndex = heap->size - 1;
    while (currentIndex > 0) {
        int parentIndex = (currentIndex - 1) / 2;
        if (heap->arr[currentIndex] < heap->arr[parentIndex]) {
            // 交换元素，保持堆的性质
            int temp = heap->arr[currentIndex];
            heap->arr[currentIndex] = heap->arr[parentIndex];
            heap->arr[parentIndex] = temp;
        } else {
            break; // 堆的性质已满足
        }
        currentIndex = parentIndex;
    }
}

// 删除堆中的最小元素
void deleteMin(struct MinHeap* heap) {
    if (heap->size == 0) {
        printf("堆为空\n");
        return;
    }

    // 将最后一个元素替换到根节点
    heap->size--;
    heap->arr[0] = heap->arr[heap->size];

    // 下移操作，维护堆的性质
    int currentIndex = 0;
    while (1) {
        int leftChild = 2 * currentIndex + 1;
        int rightChild = 2 * currentIndex + 2;
        int minIndex = currentIndex;

        if (leftChild < heap->size && heap->arr[leftChild] < heap->arr[minIndex]) {
            minIndex = leftChild;
        }
        if (rightChild < heap->size && heap->arr[rightChild] < heap->arr[minIndex]) {
            minIndex = rightChild;
        }

        if (minIndex != currentIndex) {
            // 交换元素，保持堆的性质
            int temp = heap->arr[currentIndex];
            heap->arr[currentIndex] = heap->arr[minIndex];
            heap->arr[minIndex] = temp;
            currentIndex = minIndex;
        } else {
            break; // 堆的性质已满足
        }
    }
}

// 打印堆的元素
void printHeap(struct MinHeap* heap) {
    for (int i = 0; i < heap->size; i++) {
        printf(" %d", heap->arr[i]);
    }
    printf("\n");
}

struct HeapItem {
   uint64_t val = 0;
   size_t *ref = NULL;
};
// the structure for the key
struct Entry {
   struct HNode node;
   std::string key;
   std::string val;
   uint32_t type = 0;
   ZSet *zset = NULL;
   // for TTLs
   size_t heap_idx = -1;
};

? ? ?堆用于对时间戳排序，Entry与时间戳相互链接。heap_idx是对应HeapItem的索引， ref指向Entry。我们再次使用了侵入式数据结构;ref指针指向heap_idx字段。

父子关系是固定的:

static size_t heap_parent(size_t i) {
    return (i + 1) / 2 - 1;
}
static size_t heap_left(size_t i) {
   return i * 2 + 1;
}
static size_t heap_right(size_t i) {
   return i * 2 + 2;
}

当孩子比父母小时，与父母交换。注意heap_idx是在交换时通过ref指针更新的。

static void heap_up(HeapItem *a, size_t pos) {
    HeapItem t = a[pos];
  while (pos > 0 && a[heap_parent(pos)].val > t.val) {
    // swap with the parent
    a[pos] = a[heap_parent(pos)];
    *a[pos].ref = pos;
    pos = heap_parent(pos);
}
    a[pos] = t;
    *a[pos].ref = pos;
}

和最小的孩子交换也是类似的。

static void heap_down(HeapItem *a, size_t pos, size_t len) {
    HeapItem t = a[pos];
while (true) {
   // find the smallest one among the parent and their kids
   size_t l = heap_left(pos);
   size_t r = heap_right(pos);
   size_t min_pos = -1;
   size_t min_val = t.val;
 if (l < len && a[l].val < min_val) {
   min_pos = l;
   min_val = a[l].val;
}
if (r < len && a[r].val < min_val) {
  min_pos = r;
}
if (min_pos == (size_t)-1) {
  break;
}
   // swap with the kid
   a[pos] = a[min_pos];
   *a[pos].ref = pos;
   pos = min_pos;
}
   a[pos] = t;
  *a[pos].ref = pos;
}

heap_update是用于更新位置的堆函数。它用于更新、插入和删除。

void heap_update(HeapItem *a, size_t pos, size_t len) {
  if (pos > 0 && a[heap_parent(pos)].val > a[pos].val) {
    heap_up(a, pos);
} else {
   heap_down(a, pos, len);
  }
}

将堆添加到我们的服务器:

// global variables
static struct {
   HMap db;
   // a map of all client connections, keyed by fd
   std::vector<Conn *> fd2conn;
   // timers for idle connections
   DList idle_list;
   // timers for TTLs
   std::vector<HeapItem> heap;
} g_data;

更新、添加和删除一个定时器到堆。只需在更新数组元素后调用heap_update即可。

// set or remove the TTL
static void entry_set_ttl(Entry *ent, int64_t ttl_ms) {
  if (ttl_ms < 0 && ent->heap_idx != (size_t)-1) {
   // erase an item from the heap
   // by replacing it with the last item in the array.
   size_t pos = ent->heap_idx;
   g_data.heap[pos] = g_data.heap.back();
   g_data.heap.pop_back();
  if (pos < g_data.heap.size()) {
   heap_update(g_data.heap.data(), pos, g_data.heap.size());
}
  ent->heap_idx = -1;
}  else if (ttl_ms >= 0) {
  size_t pos = ent->heap_idx;
  if (pos == (size_t)-1) {
  // add an new item to the heap
  HeapItem item;
  item.ref = &ent->heap_idx;
  g_data.heap.push_back(item);
   pos = g_data.heap.size() - 1;
}
  g_data.heap[pos].val = get_monotonic_usec() + (uint64_t)ttl_ms * 1000;
  heap_update(g_data.heap.data(), pos, g_data.heap.size());
 }
}

后面懒得写了。