数据密集型应用系统设计

1：索引是B+tree

非叶子节点不存储数据，叶子节点存储数据，并且节点内是顺序链表

2：  红黑树（时间复杂度O(log n)）

1：  map/set，

2:    epoll的fd管理快速查删改

3:    nginx的timer 时间是有序的，快速定位当前最小定时器

3： hashmap

code：

#include <stdio.h>

#include <stdlib.h>

struct node{

   int key;

   int val;

   struct node *next;

};

struct table{

   int size;

   struct node **list;

};

struct table *createTable(int size){

   struct table *t = (struct table*)malloc(sizeof(struct table));

   t->size = size;

   t->list = (struct node**)malloc(sizeof(struct node*)*size);

   int i;

   for(i=0;i<size;i++)

       t->list[i] = NULL;

   return t;

}

int hashCode(struct table *t,int key){

   if(key<0)

       return -(key%t->size);

   return key%t->size;

}

void insert(struct table *t,int key,int val){

   int pos = hashCode(t,key);

   struct node *list = t->list[pos];

   struct node *newNode = (struct node*)malloc(sizeof(struct node));

   struct node *temp = list;

   while(temp){

       if(temp->key==key){

           temp->val = val;

           return;

       }

       temp = temp->next;

   }

   newNode->key = key;

   newNode->val = val;

   newNode->next = list;

   t->list[pos] = newNode;

}

int lookup(struct table *t,int key){

   int pos = hashCode(t,key);

   struct node *list = t->list[pos];

   struct node *temp = list;

   while(temp){

       if(temp->key==key){

           return temp->val;

       }

       temp = temp->next;

   }

   return -1;

}

int main(){

   struct table *t = createTable(5);

   insert(t,2,3);

   insert(t,5,4);

   printf("%d",lookup(t,5));

   return 0;

}