数据密集型应用系统设计
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;
}
