# Big Table

## Big Table

## Big Table的读

(1)给定一个key，Big table 先从内存的memtable(本质上是skiplist)找对应value, 因为memtable的数据是最新的，如果memtable找不到，则会在硬盘里的每个Sstable内部，逐个二分查找(Sstable里的key是有序的)

## Big Table的写

(1) 给定key-value pair，先在内存的memtable查看key是否存在，有的话直接overwrite

(2) 否则在硬盘里的Sstable逐个通过Sstable里面的Bloom Filter查询key是否在里面，如果在则通过索引快速寻找key，然后overwrite。如果所有Sstable都找不到的话，就在内存直接写到memtable里

(3) 每个写操作都是先写一次write ahead log, 这样如果突然断电，memtable的数据丢失时，可以通过log重写恢复

## Write Ahead Log

## Bloom Filter