數(shù)據(jù)密集型應用系統(tǒng)設計
1：索引是B+tree
非葉子節(jié)點不存儲數(shù)據(jù)，葉子節(jié)點存儲數(shù)據(jù)勉抓，并且節(jié)點內(nèi)是順序鏈表
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;
}
