• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            xiaoxiaoling

            C++博客 首頁 新隨筆 聯系 聚合 管理
              17 Posts :: 2 Stories :: 9 Comments :: 0 Trackbacks

            Redis是工作中很常用的,這里將比較普遍使用的結構研究了下做個備忘。

             

            hash

            實現和dnspod的dataset半斤八兩,本質上是個二維數組,通過將key哈希作為一維的下表,第二維的數組存相同哈希的元素,查找使用遍歷的方式,所以這里redis做了優化,當滿足條件的時候(數組數量太大)會進行rehash,動態擴大桶的數量來減少最后一維遍歷的次數.

            函數名稱

            作用

            復雜度

            dictCreate

            創建一個新字典

            O(1)

            dictResize

            重新規劃字典的大小

            O(1)

            dictExpand

            擴展字典

            O(1)

            dictRehash

            對字典進行N步漸進式Rehash

            O(N)

            _dictRehashStep

            對字典進行1步嘗試Rehash

            O(N)

            dictAdd

            添加一個元素

            O(1)

            dictReplace

            替換給定key的value值

            O(1)

            dictDelete

            刪除一個元素

            O(N)

            dictRelease

            釋放字典

            O(1)

            dictFind

            查找一個元素

            O(N)

            dictFetchValue

            通過key查找value

            O(N)

            dictGetRandomKey

            隨機返回字典中一個元素

            O(1)

             

            字典結構

            typedef struct dict {

                // 類型特定函數

                dictType *type;

                // 私有數據

                void *privdata;

                // 哈希表

                dictht ht[2];

                // rehash 索引

                // 當 rehash 不在進行時,值為 -1

                int rehashidx; /* rehashing not in progress if rehashidx == -1 */

                // 目前正在運行的安全迭代器的數量

                int iterators; /* number of iterators currently running */

            } dict;

            這里哈希表有兩個,一般都用ht[0],當需要rehash的時候會創建一個比ht[0]大的 2 的 N 次方的ht[1],然后漸進式的將數據dictEntry移過去(除了定時的rehash,在每次操作哈希表時都會_dictRehashStep),完成后將ht[1]替換ht[0]

             

            zset

            zset本質就是list,只不過每個元素都有若干個指向后繼span長的指針,這樣簡單的設計大大提高了效率,使得可以比擬平衡二叉樹,查找、刪除、插入等操作都可以在對數期望時間內完成,對比平衡樹,跳躍表的實現要簡單直觀很多。

             

             

            /* ZSETs use a specialized version of Skiplists */

            /*

             * 跳躍表節點

             */

            typedef struct zskiplistNode {

                // 成員對象

                robj *obj;

                // 分值

                double score;

                // 后退指針

                struct zskiplistNode *backward;

                // 層

                struct zskiplistLevel {

                    // 前進指針

                    struct zskiplistNode *forward;

                    // 跨度

                    unsigned int span;

                } level[];

            } zskiplistNode;

             

            /*

             * 跳躍表

             */

            typedef struct zskiplist {

                // 表頭節點和表尾節點

                struct zskiplistNode *header, *tail;

                // 表中節點的數量

                unsigned long length;

                // 表中層數最大的節點的層數

                int level;

            } zskiplist;

             

            /*

             * 有序集合

             */

            typedef struct zset {

             

                // 字典,鍵為成員,值為分值

                // 用于支持 O(1) 復雜度的按成員取分值操作

                dict *dict;

                // 跳躍表,按分值排序成員

                // 用于支持平均復雜度為 O(log N) 的按分值定位成員操作

                // 以及范圍操作

                zskiplist *zsl;

             

            } zset;

             

            雖然這種方式排序查找很快,但是修改的話就得多做些工作了

             

            /* Delete an element with matching score/object from the skiplist.

             *

             * 從跳躍表 zsl 中刪除包含給定節點 score 并且帶有指定對象 obj 的節點。

             *

             * T_wrost = O(N^2), T_avg = O(N log N)

             */

            int zslDelete(zskiplist *zsl, double score, robj *obj)

             

            intset

            typedef struct intset {  

            uint32_t encoding; //所使用類型的長度,4\8\16  

            uint32_t length; //元素個數  

            int8_t contents[]; //保存元素的數組  

            } intset;  

             

            intset其實就是數組,有序、無重復地保存多個整數值,查找用的是二分查找 * T = O(log N),添加的話在找到對應的數組中應該存在的位子后使用memmove向后移出空位填補(當然需要先realloc預分配空間),同理刪除也是用memmove向前移動

             

            set

            當使用整數時,使用intset,否則使用哈希表

             

             

            其他的關于網絡事件處理,epoll,回調,拆包都和正常使用差不多,關于錯誤處理EINTR(系統調用期間發生中斷)和EAGAIN 繼續重試而如果是EPOLLHUP或EPOLLERR則讓io該讀讀該寫寫,有錯處理就是了。

             

             

            posted on 2017-01-24 18:13 clcl 閱讀(267) 評論(0)  編輯 收藏 引用
            亚洲国产另类久久久精品小说| 国产精品久久久久久久午夜片 | 色综合久久中文字幕综合网 | 久久影院久久香蕉国产线看观看| 久久久久久国产a免费观看不卡| 久久精品国产色蜜蜜麻豆| 中文精品99久久国产 | 亚洲va久久久噜噜噜久久狠狠| 久久久精品人妻一区二区三区四| 久久国产免费观看精品| 亚洲国产成人久久笫一页| 久久水蜜桃亚洲av无码精品麻豆| 久久伊人精品青青草原高清| 亚洲欧洲精品成人久久曰影片 | 久久国产精品-久久精品| 久久夜色精品国产亚洲| 999久久久免费国产精品播放| 国产69精品久久久久观看软件| 久久精品国产亚洲欧美| 老色鬼久久亚洲AV综合| 尹人香蕉久久99天天拍| 久久久久亚洲AV无码专区网站 | 国产精品久久久久jk制服| 久久久久亚洲av成人无码电影 | 久久人妻AV中文字幕| 久久夜色精品国产| 国产精品99久久不卡| 日韩精品国产自在久久现线拍 | 亚洲国产精品综合久久一线| 青青草国产精品久久| 97久久国产亚洲精品超碰热| 久久中文字幕人妻丝袜| 久久91精品国产91| 中文精品99久久国产| 久久嫩草影院免费看夜色| 久久www免费人成看国产片| 国产日韩欧美久久| 久久夜色精品国产| 久久只有这精品99| 久久人人爽人人爽人人av东京热| 国产美女亚洲精品久久久综合 |