鍏堝喅鐭ヨ瘑馃鑷粠寮€濮嬮€氳繃鍗氬璁板綍瀛︿範鍐呭鍜屾暣鐞嗙煡璇嗗悗锛屾垜姣斾互鍓嶆洿娲昏穬浜嗭紝铏界劧鏈川鏄负浜嗚褰曞拰鏁寸悊锛屼絾杩樻槸蹇嶄笉浣忓叧蹇冨悇澶у崥瀹㈢珯鐨勯槄璇婚噺鍜岀偣璧為噺鍜岃瘎璁洪噺锛堣櫧鐒惰繕鏄皯寰楀彲鎬滃搱鍝堝搱锛夛紝鏈変簺鍗氬绔欐湁鑷繁鐨勪笓灞炵Н鍒嗭紝鐢氳嚦鎺掕姒滐紝鍋跺皵鐐逛竴涓嬶紝鐪嬬湅鑳戒笉鑳藉嚭鐜板湪涓婇潰~锛堝樆鍢粇姊﹂噷浠€涔堥兘鏈夛級Q锛氶偅涔堣繖涓帓琛屾搴旇鎬庝箞瀹炵幇鍛紵锛堝己琛屽洖绛旈棶棰橈紒锛夌瓟锛氱畝鍗曪紒鏁版嵁搴撴槸鐢ㄤ竴寮犺〃鏉ョ淮鎶ょ殑锛屾寜鏁存暟鍊煎瓧娈电殑澶у皬鎺掑簭鏄笉琛岀殑~纭疄鍙锛屼絾鏄洜涓虹綉绔欏苟鍙戦噺澶э紝闇€瑕佸揩閫熷搷搴旓紝鎵€浠ュ繀椤荤敤缂撳瓨鐨勫府鍔╋紝鑰宺edis涓伆濂芥湁涓€涓熀鏈殑鏁版嵁缁撴瀯绗﹀悎杩欎釜闇€姹傦紝閭ｅ氨鏄疭ortedset锛堟湁搴忛泦鍚堬級锛屽畠涓嶈兘鍍廠et锛堥泦鍚堬級閭ｆ牱鏈夐噸澶嶇殑鍏冪礌锛屼絾鏄畠鏈夋洿澶氱殑鎺掑簭鍔熻兘锛岃€屼笖瀹冩槸鑷姩鎺掑簭鐨勶紝涓嶉渶瑕佺淮鎶わ紝灏辨槸浣犲鍔犳垨鑰呮洿鏂板厓绱狅紝搴曞眰鑷姩甯綘鎺掑簭銆傛墍浠ュ綋浣犻渶瑕佷竴涓湁搴忎笖涓嶉噸澶嶇殑闆嗗悎鍒楄〃鏃讹紝閭ｄ箞Sortedset浼氭槸涓€涓笉閿欑殑閫夋嫨銆係ortedset鐨勫簳灞傚疄鐜颁娇鐢ㄤ簡redis浣跨敤鐨勬瘮杈冩湁浠ｈ〃鎬х殑鏁版嵁缁撴瀯鈥斺€攕kiplist锛岃繖涔熸槸鎴戜滑浠婂ぉ瑕佽鐨勪富瑕佸唴瀹广€傚畠鍦╮edis涓槸濡備綍璧峰埌鎺掑簭浣滅敤鐨勶紝鍙堟槸濡備綍瀹炵幇鐨勫憿锛熺緤姣涘竷锛熻繕鏄粠澶存⒊鐞嗗惂~涓崕鏂囧寲鍗氬ぇ绮炬繁鎴戜滑甯歌杩欏彞璇濓細涓崕鏂囧寲鍗氬ぇ绮炬繁锛涗腑鍗庢枃鍖栧崥澶х簿娣憋紱浣嗘湁鏃跺鏋滄病鏈夋纭悊瑙ｅ叾鍚箟锛屽畠浼氫骇鐢熼€傚緱鍏跺弽鐨勬晥鏋溿€傛瘮濡傝烦琛紝鍏ㄧО鏄烦琛紙鎽樿嚜鐧剧鍏ㄤ功锛夛紝濡傛灉娌℃湁鐪嬪埌璺宠〃鐨勮嫳鏂囧崟璇峴kiplist锛屽彲鑳戒細璇細銆傝繖涓烦杩囦笉鏄烦璺冦€傛剰鎬濇槸鈥滆烦杩囷紝鐪佺暐鈥濓紝鎵€浠ユ垜涓汉璁や负缈昏瘧鎴愨€滆烦杩囧垪琛ㄢ€濆彲鑳芥洿鍚堥€傦紝浣嗕綘涓嶅繀鎷呭績銆傜浉淇″鏋滀綘鐞嗚В浜唖kiplist鍦ㄨ嫳鏂囦腑鐨勫師鎰忥紝灏嗕細甯姪浣犳洿濂界殑缁х画涓嬪幓銆傜户缁槄璇讳互浜嗚В璺宠浆琛ㄣ€傛帓搴忥紝浣犳€庝箞鐪嬶紵鍏堜粠鏈€鍩烘湰鐨勬暟鎹粨鏋勮璧凤細Array鉂庢暟缁勫湪鍐呭瓨涓槸杩炵画鐨勩€傚鏋滃闇€瑕佹帓搴忕殑鍏冪礌杩涜澧炲垹鏀规煡锛屽氨浼氣€滅壍涓€鍙戣€屽姩鍏ㄨ韩鈥濄€傚娍蹇呬細鍋氬ぇ閲忕殑鍐呭瓨鍒犻櫎鎴栫Щ鍔ㄦ搷浣滐紱鎵€浠ラ櫎闈炴垜浠兂缁存姢涓€缁勫浐瀹氱殑鍏冪礌锛屽惁鍒欏叾浠栨儏鍐典笉闇€瑕佽€冭檻鏁扮粍锛屾墍浠ass銆傞摼琛ㄢ渽浠ヤ笂鎯呭喌鍦ㄩ摼琛ㄤ腑鏄笉瀛樺湪鐨勶紝閾捐〃鐨勭壒鐐规槸瀛樺偍绾挎€ц〃鐨勬暟鎹粨鏋勶紱娣诲姞銆佹洿鏂般€佸垹闄ょ瓑鎿嶄綔鏃犻潪灏辨槸鏀瑰彉鎸囬拡鎸囧悜鐨勫湴鍧€锛岃繖鏄竴涓笉閿欑殑閫夋嫨銆傚搱甯岃〃鉂庡搱甯岃〃鍏跺疄鏄棤搴忕殑銆傚湪鍝堝笇琛ㄤ笂鍙兘鏌ユ壘鍗曚釜key锛屼笉閫傚悎鑼冨洿鏌ユ壘锛屾墍浠ヤ篃閫氳繃浜嗐€俆ree鉁匱ree鍏跺疄鏄帓搴忕殑浼樿川閫夋嫨锛屼絾鏄粠缁撴灉鏉ョ湅锛宺edis骞舵病鏈変娇鐢ㄥ畠銆傚師鍥犲厛涓嶅垪涓撅紝鍚庨潰浼氳缁嗚鏄庛€傛櫘閫氶摼琛ㄨ兘婊¤冻闇€姹傚悧锛熻烦琛ㄥ浣曚紭鍖栧憿锛熸垜浠厛鏉ョ湅涓€涓櫘閫氱殑鏈夊簭閾捐〃锛氬鏋滄垜瑕佹坊鍔犳柊鐨勫厓绱?8锛岄偅涔堝彧鑳戒粠澶磋妭鐐瑰紑濮嬶紝閫氳繃next鎸囬拡鎵惧埌绗竴涓厓绱?锛屽啀閫氳繃next鎵惧埌涓嬩竴涓厓绱?pointer,渚濇绫绘帹锛岀洿鍒版壘鍒扮涓€涓ぇ浜庣瓑浜庣殑鍏冪礌鍔犲叆锛屽嵆鍏冪礌19锛屽ぇ浜?8锛屾墍浠ユ垜浠簲璇ュ湪鍏冪礌19涔嬪墠鍔犲叆鍏冪礌18锛屽苟浼犻€?涓寚閽堬紙绠€绉颁负绾㈣壊绠ご鐨勬暟閲忥級鎸囧悜鏈€鍚庣殑缁撴灉銆傚彲浠ョ湅鍑猴紝閾捐〃瓒婇暱锛屾彃鍏ヤ綅缃秺闈犲悗锛岃€楁椂瓒婂锛屾椂闂村鏉傚害涓篛(n)銆傛€绘劅瑙夊彲浠ヤ紭鍖栦竴涓嬶紒鍐嶆鎻愪竴涓嬭繖鍙ヨ瘽锛氫紬鎵€鍛ㄧ煡锛宺edis鏄竴涓拷姹傛€ц兘鐨勭▼搴忋€傚湪杩欓噷鎻掑叆涓€涓皬鐭ヨ瘑锛?0澶氬勾鍓嶇殑1990骞达紝WilliamPu鍙戞槑浜嗚烦杞〃锛坖umptable锛夛紝骞朵粠鐧剧鍏ㄤ功涓憳鍙栦簡鍙戞槑浜篧illiamPu瀵硅烦杞〃鐨勮瘎浠凤細Jumplistispossibleinmanyapplications涓€涓暟鎹瀹炵幇鐨勭粨鏋勮€屼笉鏄钩琛℃爲銆傝烦璺冨垪琛ㄧ殑绠楁硶涓庡钩琛℃爲鍏锋湁鐩稿悓鐨勬笎杩戦鏈熸椂闂寸晫闄愶紝骞朵笖鏇寸畝鍗曘€佹洿蹇苟涓斾娇鐢ㄦ洿灏戠殑绌洪棿銆傚ソ鐨勶紒閫氳繃杩欐娴嬭瘎锛屾垜浠笉浠呭璺宠〃鏈変簡涓€涓ぇ姒傜殑浜嗚В锛岃繕椤轰究娑夊強鍒颁竴閬撳父瑙佺殑鐩稿叧闈㈣瘯棰樸€備綔鑰呰璺宠〃绠€鍗曪紵鍝噷瀹规槗锛熶綘鎬庝箞璁や负锛佽烦琛ㄨ烦琛紝涔嬫墍浠ュ彨璺宠〃鏄洜涓哄畠鍙互璺硚锛堜笉鏄洜涓鸿烦琛ㄥ彲浠ラ€氳繃鑺傜偣鐨勮浆绉绘洿蹇殑鎵惧埌鐩爣鍊硷紝鎴戜滑缁х画浣跨敤涓婇潰鐨勬暟鎹紝鑰屾槸鐩存帴鍒囨崲鍒拌烦琛ㄧ殑鏁版嵁缁撴瀯涓句釜鏍楀瓙馃尠锛氱洿瑙変笂锛屾湁浜涘厓绱犲ソ鍍忓浜嗕竴灞傦紝浣嗘槸鎴戜滑涓嶇煡閬撲负浠€涔堬紝涓嶈繃涓嶇敤鎷呭績锛屾垜浠皾璇曟寜鐓ц繖涓粨鏋勬坊鍔犳柊鐨勫厓绱犮€?8涔嬪墠锛屾垜浠槸浠庣涓€灞傚紑濮嬶紝浣嗘槸杩欐鎴戜滑鏄粠绗簩灞傦紝涔熷氨鏄疞2鑺傜偣寮€濮嬶紝閫氳繃next鎸囬拡璺宠繃鍏冪礌2锛岀洿鎺ユ寚鍚戝厓绱?锛屽啀鎸囧悜鍏冪礌7锛岀洿鍒板厓绱?9锛岃繖澶т簬18鍙峰厓绱狅紝鐒跺悗閫氳繃鍚庡悜鎸囬拡鎵惧埌鍓嶉潰鐨?7鍙峰厓绱犲拰18鍙峰厓绱犻兘姣斿畠澶э紝鎵€浠ユ垜浠渶鍚庡湪杩欓噷娣诲姞鍏冪礌锛岄€氳繃5涓寚閽堬紙绠€绉扮孩鑹茬澶寸殑鏁板瓧锛夊鍧€鏈€缁堢粨鏋?.鍜屼箣鍓嶇殑绠€鍗曢摼琛ㄧ浉姣旓紝闇€瑕佺敤8涓寚閽堟潵瀵诲潃銆傝烦琛ㄧ殑澶嶆潅搴︾◢寰綆涓€鐐广€備絾鎴戜滑杩樹笉婊¤冻銆傝繖娆℃垜浠妸涓€浜涘厓绱犵殑灞傛暟澧炲姞鍒?灞傛潵鐪嬩竴涓嬨€傝繖娆″皯浜嗭紝閫氳繃4涓寚閽堬紙绠€绉扮孩鑹茬澶寸殑涓暟锛夊氨鍙互瀵诲潃鍒版渶缁堢殑缁撴灉銆俿kiplist鐨勫鍧€閫昏緫鍙互绠€鍗曟鎷负锛氫粠鏈€楂樺眰寮€濮嬪鍧€锛屽鏋滃綋鍓嶈妭鐐圭殑next鎸囬拡鎸囧悜null锛屽垯寰€涓嬩竴灞傦紝濡傛灉鏄寚鍚戠殑涓嬩竴涓厓绱犵殑鍊糿ext鎸囬拡灏忎簬鏌ユ壘鍊硷紝缁х画寰€涓嬭蛋锛屽ぇ浜庡垯璋冪敤鍚戝悗鍚戝悗鎸囬拡鏌ユ壘涓婁竴涓厓绱犺繘琛屾瘮杈冿紝鐩村埌鎵惧埌瀵瑰簲浣嶇疆銆傚厓绱犲垎鏁颁細鐩稿悓鍚楋紵鏄殑锛岃繖鏃跺€欎細鎸夌収鏁版嵁obj鐨勫瓧鍏搁『搴忚繘琛屾帓搴忥紝鍙互寰堝鏄撶悊瑙ｄ紭鍏堢骇涓?~9锛孉~Z锛宎~z銆傛湁娌℃湁娉ㄦ剰鍒颁笂闈㈢殑杩囩▼鏈夌偣绫讳技浜庝簩鍒嗘煡鎵撅紝鎴栬€呰n鐐规煡鎵撅紝鐞嗘兂鎯呭喌涓嬪皢鏃堕棿澶嶆潅搴︿粠鍘熸潵鐨凮(n)闄嶄綆鍒癘(logn)銆傝烦琛ㄨ妭鐐硅瑙ｉ鍏堟垜浠湅涓€涓嬭烦琛ㄨ妭鐐圭粨鏋勭殑瀹氫箟锛歵ypedefstructzskiplistNode{//鍚庡悜鎸囬拡structzskiplistNode*backward;//寰楀垎鍙屽€嶅緱鍒嗭紱//鎴愬憳瀵硅薄robj*obj;//LayerstructzskiplistLevel{//鍓嶅悜鎸囬拡structzskiplistNode*forward;//璺ㄥ害鏃犵鍙锋暣鏁拌法搴︼紱}level[];}zskiplistNode;鐪嬪埌鍏蜂綋鐨剆kiplist鑺傜偣缁撴瀯锛屾垜浠氨鐭ラ亾棰濆鐨勫眰鏄粠鍝噷鏉ョ殑浜嗐€傛垜浠笂闈㈢殑渚嬪瓙鏄竴涓悊鎯崇姸鎬侊紝灞傛暟浠?鍒皀寰幆鍑虹幇锛屼絾鏄鏋滀綘淇敼鏁版嵁锛屾瘮濡傚鍒犳敼鏌ワ紝濡傛灉杩樻槸鎸夌収鈥滃眰鏁颁粠1鍒皀寰幆鍑虹幇鈥濈殑鍘熷垯銆嬶紝鍏跺疄灏卞拰涓婇潰璇寸殑闃垫硶涓€鏍封€斺€斾竴鏍规瘺鍙戠壍涓€鍙戣€屽姩鍏ㄨ韩锛岄渶瑕佺淮鎸佸眰鏁帮紝鎵€浠ュ緱涓嶅伩澶便€備簬鏄箮锛宺edis閲囩敤浜嗕竴绉嶆湁瓒ｇ殑鏂瑰紡鏉ヨ缃妭鐐圭殑灞傛暟銆傞鍏堬紝纭繚鎵€鏈夎妭鐐归兘鏈変竴绾ф寚閽堛€傞偅涔堟瘡鏈変竴涓柊鐨勮妭鐐癸紝鑺傜偣鐨勫眰鏁版槸涓嶆槸杩樿缁х画澧炲姞鍛紵璁╂垜浠姏涓€鏋氱‖甯侊紝鍙姝ｉ潰鏈濅笂灏变竴鐩村姞锛岀洿鍒板弽闈㈠嚭鐜板氨鍋滄銆傞珮杈?2灞傘€傜▼搴忓綋鐒朵笉鍙兘鎶涚‖甯侊紝涓句釜鏍楀瓙馃尠锛屽叾瀹炴槸閫氳繃while寰幆瀹炵幇鐨勶紝澧炲姞灞傛暟鐨勬鐜囨槸1/4锛屽拰鎶涚‖甯併€傛牴鎹笂杩版鐜囷紝鎴戜滑鍙互寰楀嚭锛氳妭鐐瑰眰鏁版濂戒负1鐨勬鐜囦负\(\frac{3}{4}\)鑺傜偣灞傛暟姝ｅソ涓?鐨勬鐜囦负\(\frac{1}{4}\cdot\frac{3}{4}\)鑺傜偣灞傛暟姝ｅソ涓?鐨勬鐜囦负\(\frac{1}{4}\cdot\frac{1}{4}\cdot\frac{3}{4}\)...姒傜巼鍒嗗竷...鍥犱负涓€涓眰闇€瑕佷竴涓寚閽堬紝閭ｄ箞涓€涓妭鐐圭殑骞冲潎鎸囬拡鏁板涓嬶細\(1\cdot\frac{3}{4}+2\cdot(\frac{1}{4}\cdot\frac{3}{4})+鈥?n\cdot(\frac{1}{4})^{n-1}\cdot\frac{3}{4}=\frac{3}{4}\cdot\sum_{i=1}^{+\infty}\cdot{n}\cdot(\frac{1}{4})^{n-1}=\frac{4}{3}\)缁忚繃涓€绯诲垪璁＄畻锛屽彲浠ュ緱鍑哄钩鍧囨瘡涓妭鐐瑰寘鍚殑鎸囬拡鏁扮害涓?.3涓€傜幇鍦ㄦ垜浠洖鏀朵紡绗斻€備竴寮€濮嬫垜浠彁鍒皉edis鏈€缁堟病鏈夐噰鐢ㄦ爲褰㈢粨鏋勩€傚叾涓竴涓師鍥犱笌鎸囬拡鐨勪釜鏁版湁鍏筹細锛堜笉鐭ラ亾鏍戠殑鏁版嵁缁撴瀯涔熸病鍏崇郴锛屽彧闇€瑕佺煡閬撴爲鐨勬寚閽堟湁涓や釜鍥哄畾鐨勬暟鍗冲彲銆?銆乴eft瀛愭爲鎸囬拡鍜屽彸瀛愭爲鎸囬拡锛夎烦琛ㄨ妭鐐圭殑鎸囬拡骞冲潎涓暟涓?.3涓紝鑰屾爲涓殑鎸囬拡涓暟鍥哄畾涓?涓紝鎸囬拡鍗犵敤涓€瀹氱殑鍐呭瓨銆傚緢鏄庢樉锛岃烦琛ㄦ瘮鏍戜娇鐢ㄧ殑鍐呭瓨灏戯紝redis鏄熀浜庡唴瀛樼殑鎿嶄綔锛岀摱棰堟渶鏈夊彲鑳芥槸鍐呭瓨澶у皬鍜岀綉缁滃甫瀹斤紝鎵€浠ヨ烦琛ㄦ瘮鏍戣妭鐪佸唴瀛樸€傞偅涔圧edis涓轰粈涔堜娇鐢╯kiplist鑰屼笉鏄爲缁撴瀯鍛紵鍏跺疄瀵逛簬杩欎釜闂锛宺edis鐨勪綔鑰呭凡缁忕粰鍑轰簡绛旀锛氭湁鍑犱釜鍘熷洜锛?锛夊畠浠笉鏄緢鍗犵敤鍐呭瓨銆傝繖鍩烘湰涓婂彇鍐充簬浣犮€傛洿鏀规湁鍏宠妭鐐瑰叿鏈夌粰瀹氱骇鍒暟鐨勬鐜囩殑鍙傛暟灏嗘瘮btrees鍗犵敤鏇村皯鐨勫唴瀛樸€?锛夋帓搴忛泦閫氬父鏄澶歓RANGE鎴朲REVRANGE鎿嶄綔鐨勭洰鏍囷紝鍗筹紝灏嗚烦杩囧垪琛ㄤ綔涓洪摼琛ㄩ亶鍘?閫氳繃姝ゆ搷浣滐紝璺宠穬鍒楄〃鐨勭紦瀛樺眬閮ㄦ€ц嚦灏戜笌鍏朵粬绫诲瀷鐨勫钩琛℃爲涓€鏍峰ソ銆?)瀹冧滑鏇存槗浜庡疄鐜般€佽皟璇曠瓑銆備緥濡傦紝鐢变簬璺宠穬鍒楄〃鐨勭畝鍗曟€э紝鎴戞敹鍒颁簡涓€涓ˉ涓侊紙宸茬粡鍦≧edismaster涓級锛屽叾涓寘鍚湪O(log(N))涓疄鐜癦RANK鐨勫寮鸿烦璺冨垪琛ㄣ€傚畠闇€瑕佸浠ｇ爜杩涜灏戦噺鏇存敼銆傛鎷捣鏉ユ湁浠ヤ笅鍑犵偣锛歴kiplist鍗犵敤鍐呭瓨涓嶅锛岃妭鐐规寚閽堢殑骞冲潎涓暟姣旀爲灏戯紙涓婇潰宸茬粡璇佹槑锛夈€係kiplist鍙互寰堝ソ鐨勫疄鐜拌寖鍥存悳绱紙鎸囨壘鍒板ぇ灏忓湪涓や釜鎸囧畾鍊间箣闂寸殑鎵€鏈夎妭鐐癸紝濡俍RANGE鍛戒护锛夛紝鏍戞瘮璺宠〃鎿嶄綔澶嶆潅锛岃€楁椂鏇村銆係kiplist寰堝鏄撳疄鐜帮紒鏍戣繕娑夊強瀛愭爲鐨勮皟鏁达紝閫昏緫澶嶆潅銆俿kiplist鍦ㄧ畻娉曞疄鐜伴毦搴︿笂姣攖ree绠€鍗曞緢澶氥€傚綋浣犻亣鍒拌繖涓潰璇曢锛岄潰璇曞畼杩樿浣犻敊鐨勬椂鍊欙紝浣犲彲浠ヨ嚜淇＄殑鍛婅瘔浠栵紝杩欏氨鏄痳edis鐨勪綔鑰呰鐨勩€傛垜鏄枃鏈殑鑻忎害浜戙€備綘涔熷彲浠ュ彨鎴戜緷浜戙€傛垜鏄竴鍚岼ava寮€鍙戦鍩熺殑灏忓鐢熴€傛枃绔犺川閲忓彲鑳戒笉鏄緢楂橈紝浣嗘垜涓€瀹氫細闈炲父鐢ㄥ績銆傝刀绱ф妸璺冲彴璧跺嚭鍘汇€傝瀹炶瘽锛屽嚑涓湀鍓嶆垜瀵硅烦琛ㄤ竴鏃犳墍鐭ャ€傚彧鐭ラ亾鐢╮edis锛屾槸涓€涓粡甯歌闂強鏈変唬琛ㄦ€х殑鏁版嵁缁撴瀯銆傚姫鍔涙秷鍖栧拰纰惧帇鍚庯紝鑷繁涔熸敹鑾烽涓般€傚鏋滃ぇ瀹朵篃鑳芥湁鎵€鏀惰幏锛岄偅鎴戝氨寰堝紑蹇冧簡~鍧氭寔鏇存柊鏂囨鏄竴涓浉褰撳ぇ鐨勬寫鎴橈紝甯屾湜鑷繁鑳藉潥鎸佷笅鍘汇€傜柅鎯呮湡闂村湪瀹跺姙鍏紝鏈夋椂闂村璇讳功銆傝涔︼紝涓嶈璁╄嚜宸卞伔鎳掞紝鍔犳补鍔犳补锛屼竴璧峰姞娌癸紒鏈€鍚庡笇鏈涚柅鎯呭揩鐐瑰ソ璧锋潵锛屽ぇ瀹跺彲浠ュ洖褰掓甯哥殑鐢熸椿~
