最近開始看leveldb的代碼，周末看了下skiplist，詳細介紹可以看http://blog.xiaoheshang.info/?p=248。基本原理就是空間換效率，多用幾個指針來換取查找插入效率。自己也嘗試寫了下，對比了下leveldb的代碼，內存控制沒有leveldb實現的好，leveldb申請的時候基本上都是以block為單位申請空間，這樣可以減少內存碎片，空間上每個節點就只會申請指定level個數的指針。以前一直記混淆 const char *p , char const *p 和char * const p的區別，前兩者代碼指向的內容不可變，后者指向的指針不可變。