文章目錄

• • • • 前言
      • 跳表結(jié)構(gòu)
      • 時(shí)間復(fù)雜度
      • 空間復(fù)雜度
      • 高效的動態(tài)插入和刪除
      • 跳表索引的動態(tài)更新
      • 總結(jié)
      • 詳細(xì)實(shí)現(xiàn)

前言

rocksdb 的memtable中默認(rèn)使用跳表數(shù)據(jù)結(jié)構(gòu)對有序數(shù)據(jù)進(jìn)行的管理，為什么呢？

同時(shí)redis 也用跳表作為管理自己有序集合的數(shù)據(jù)結(jié)構(gòu)，為什么他們不選擇用紅黑樹來管理(同樣能夠提供高效的插入，查找，刪除操作，而且各種語言都已經(jīng)封裝好了很多輪子),就選擇跳表來實(shí)現(xiàn)？

今天就來仔細(xì)探討一下這個(gè)數(shù)據(jù)結(jié)構(gòu)。

跳表結(jié)構(gòu)

對于一個(gè)單鏈表來說，即使鏈表中存儲的數(shù)據(jù)結(jié)構(gòu)是有序的，想要查找一個(gè)元素也需要從頭到尾進(jìn)行查找，時(shí)間復(fù)雜度是O(n)。

提高查效率的一種辦法就是建立索引，對鏈表建立一級索引，每兩個(gè)節(jié)點(diǎn)提取一個(gè)索引節(jié)點(diǎn)到上一級，把抽取出來的一級叫做索引。如下圖，down就是索引節(jié)點(diǎn)指向節(jié)點(diǎn)的指針:

此時(shí)如果我們想要查找某個(gè)節(jié)點(diǎn)，比如18?？梢韵仍谒饕龑颖闅v，當(dāng)遍歷到索引層節(jié)點(diǎn)值為13時(shí)，發(fā)現(xiàn)沒有next指針了，此時(shí)下降到原始節(jié)點(diǎn)層，繼續(xù)遍歷。這個(gè)時(shí)候只需要遍歷一個(gè)節(jié)點(diǎn)就能訪問到數(shù)值為18的節(jié)點(diǎn)了。

這樣的話原來要找節(jié)點(diǎn)18，需要遍歷8個(gè)節(jié)點(diǎn)，此時(shí)只需要遍歷6個(gè)節(jié)點(diǎn)了，查找效率提高了。那如果我們再增加一級索引，效率會不會更高呢？還是在第一級索引節(jié)點(diǎn)的基礎(chǔ)上再創(chuàng)建一級索引，如下圖：

在查找部分節(jié)點(diǎn)的情況下效率能夠更高，因?yàn)檫@里舉例的數(shù)據(jù)量較小，查看如下數(shù)據(jù)，有64個(gè)原始節(jié)點(diǎn)，按照如上的思路建立了五級索引。

此時(shí)查找節(jié)點(diǎn)62，原始鏈表需要遍歷62個(gè)節(jié)點(diǎn)，此時(shí)只需要遍歷11個(gè)節(jié)點(diǎn)即可訪問到，在數(shù)據(jù)量較為龐大的情況下效率提升非常明顯。

時(shí)間復(fù)雜度

單鏈表中查找一個(gè)節(jié)點(diǎn)的效率是O(n)，那么跳表中查找一個(gè)節(jié)點(diǎn)的時(shí)間復(fù)雜度是多少呢？
按照我們上面所說，每兩個(gè)原始節(jié)點(diǎn)抽取為一個(gè)索引節(jié)點(diǎn)的思路。

假設(shè)現(xiàn)在有n個(gè)節(jié)點(diǎn)，每兩個(gè)節(jié)點(diǎn)抽取一個(gè)索引節(jié)點(diǎn)，那么第一級索引節(jié)點(diǎn)的個(gè)數(shù)：n/2，第二級索引節(jié)點(diǎn)：n/4，第三節(jié)索引節(jié)點(diǎn)：n/8，依次第k級索引節(jié)點(diǎn)：n/(2^k)

假設(shè)索引有h級，最高級的索引有2個(gè)結(jié)點(diǎn)。通過上面的公式，我們可以得到n/(2h)=2，從而求得h=log2n-1。如果包含原始鏈表這一層，整個(gè)跳表的高度就是log2n。
我們在跳表中查詢某個(gè)數(shù)據(jù)的時(shí)候，如果每一層都要遍歷m個(gè)結(jié)點(diǎn)，那在跳表中查詢一個(gè)數(shù)據(jù)的時(shí)間復(fù)雜度就是O(m*logn)。

如何確定m的數(shù)值是多少呢，按照上面的索引結(jié)構(gòu)，從最頂層的索引層開始遍歷一直到最底層，每一級索引最多需要遍歷3個(gè)節(jié)點(diǎn)。
證明如下：

• 假設(shè)我們要查找的數(shù)據(jù)是x，在第k級索引中
• 遍歷到y(tǒng)結(jié)點(diǎn)之后，發(fā)現(xiàn)x大于y，小于后面的結(jié)點(diǎn)z，所以我們通過y的down指針，從第k級索引下降到第k-1級索 引
• 在第k-1級索引中，y和z之間只有3個(gè)結(jié)點(diǎn)(包含y和z),即我們在K-1級索引中最多只需要遍歷3個(gè)結(jié)點(diǎn)，依次類推，每一級索引都最多只需要遍歷3個(gè)結(jié) 點(diǎn)。

所以我們可以得到m=3這樣的一個(gè)結(jié)論，則在跳表中查詢?nèi)我庖粋€(gè)節(jié)點(diǎn)的時(shí)間復(fù)雜度都為O(logn)，效率和二分查找一樣。

但是問題也很明顯，索引節(jié)點(diǎn)消耗內(nèi)存空間，這是以空間換時(shí)間的方式來達(dá)到優(yōu)化的目的，接下來我們看看空間的消耗

空間復(fù)雜度

假設(shè)原始鏈表大小為n,我們前面也說過之上的索引節(jié)點(diǎn)的個(gè)數(shù)依次為：
第一級索引節(jié)點(diǎn)的個(gè)數(shù)：n/2，第二級索引節(jié)點(diǎn)：n/4，第三節(jié)索引節(jié)點(diǎn)：n/8，依次第k級索引節(jié)點(diǎn)：n/(2^k)，直到剩下兩個(gè)索引節(jié)點(diǎn)

這幾級索引節(jié)點(diǎn)的總和：n/2 + n/4 + n/8 +… 8 + 4 +2 = n -2
可以看出跳表的空間復(fù)雜度是O(n)。也就是說，如果將包含n個(gè)結(jié)點(diǎn)的單鏈表構(gòu)造成跳表，我們需要額外再用 接近n個(gè)結(jié)點(diǎn)的存儲空間。那我們有沒有辦法降低索引占用的內(nèi)存空間呢?

之前我們是每兩個(gè)節(jié)點(diǎn)抽取一個(gè)索引節(jié)點(diǎn)，同樣我們可以每三個(gè)節(jié)點(diǎn)抽取一個(gè)索引節(jié)點(diǎn)，示意圖如下：

依次總的索引節(jié)點(diǎn)的個(gè)數(shù)為：n/3 + n/9 + n/27 +… + 9 + 3 = n /2
雖然還是O(n)的空間復(fù)雜度，但是整體比上面的抽取方式少占用一般的空間。且實(shí)際開發(fā)過程中，原始鏈表中存儲的大都是數(shù)據(jù)量龐大的數(shù)據(jù)，索引節(jié)點(diǎn)僅僅存儲一些關(guān)鍵數(shù)據(jù)以及指針，基本的空間消耗并不會很大，可以忽略不計(jì)得。

高效的動態(tài)插入和刪除

插入數(shù)據(jù)和查找數(shù)據(jù)的時(shí)間復(fù)雜度一樣，單鏈表的插入性能消耗O(n)在查找插入位置上，而真正的插入只需要O(1)的時(shí)間。同樣，跳表的插入也是消耗在查找的時(shí)間復(fù)雜度上O(logn)。

刪除的時(shí)候，我們在找到原始鏈表中的節(jié)點(diǎn)之后，如果該節(jié)點(diǎn)還出現(xiàn)在索引節(jié)點(diǎn)之中，我們除了要刪除原始鏈表中的節(jié)點(diǎn)，還需要刪除索引層中的節(jié)點(diǎn)。

跳表索引的動態(tài)更新

當(dāng)我們不停地往跳表中插入數(shù)據(jù)時(shí)，如果我們不更新索引，就有可能出現(xiàn)某2個(gè)索引結(jié)點(diǎn)之間數(shù)據(jù)非常多的情況。極端情況下，跳表還會退化成單鏈表。
如下這種情況：

紅黑樹、AVL樹這樣平衡二叉樹，它們是通過左右旋的方式保持左右子樹的大小平衡(如果不了解也沒關(guān)系，我們后面會講)，而跳表是通 過隨機(jī)函數(shù)來維護(hù)前面提到的“平衡性”。

過程如下：

• 通過一個(gè)隨機(jī)函數(shù)，來決定將這個(gè)結(jié)點(diǎn)插入到哪幾級索引中，比如隨機(jī)函數(shù)生成了K
• 查找當(dāng)前節(jié)點(diǎn)要插入的原始節(jié)點(diǎn)的位置
• 基于該位置,從原始鏈表層向上，每層建立一個(gè)指向該節(jié)點(diǎn)的down指針，直到第K層
  如下節(jié)點(diǎn)6 插入該跳表，并且隨機(jī)函數(shù)生成的K=2，即對6創(chuàng)建索引節(jié)點(diǎn)直到第二層
  

總結(jié)

綜上描述，我們了解了跳表的查找，插入，刪除，更新的過程，為什么rocksdb和redis都想要使用跳表作為自己的有序集合的管理結(jié)構(gòu)呢？

像redis和rocksdb 都提供以下核心的數(shù)據(jù)操作：

• 插入一個(gè)數(shù)據(jù)
• 刪除一個(gè)數(shù)據(jù)
• 查找一個(gè)數(shù)據(jù)
• 查找一個(gè)區(qū)間數(shù)據(jù)[52,100]
• 不斷輸出一個(gè)有序序列

以上插入，查找，刪除，迭代輸出的操作跳表和紅黑樹的效率接近，但是range查找則紅黑樹沒有跳表高
在區(qū)間查找的時(shí)候，跳表只需要找到區(qū)間的第一個(gè)元素即可順序遍歷即可（元素是有序的），但是紅黑樹每一個(gè)元素都需要相同的復(fù)雜度。

但是跳表并沒有紅黑樹的接口通用，很多語言都提供紅黑樹的實(shí)現(xiàn)接口，跳表還需要自己實(shí)現(xiàn)。

詳細(xì)實(shí)現(xiàn)

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#include <cstring>
#include <random>
#include <ctime>
using namespace std;/*** 跳表的一種實(shí)現(xiàn)方法。* 跳表中存儲的是正整數(shù)，并且存儲的是不重復(fù)的。* *  跳表結(jié)構(gòu):* *  第K級           1           9*  第K-1級         1     5     9*  第K-2級         1  3  5  7  9*  ...             ....*  第0級(原始鏈表)  1  2  3  4  5  6  7  8  9*/const int MAX_LEVEL = 16;/*** @brief 節(jié)點(diǎn)
*/
class CNode
{
public:CNode();~CNode();std::string toString();/*** @brief 獲取索引鏈表*/CNode** GetIdxList();/*** @brief 設(shè)置數(shù)據(jù)*/void SetData(int v);/*** @brief 獲取數(shù)據(jù)*/int GetData();/*** @brief 設(shè)置最大索引級別*/void SetLevel(int l);
private:/**當(dāng)前節(jié)點(diǎn)的值*/int m_data;/** * 當(dāng)前節(jié)點(diǎn)的每個(gè)等級的下一個(gè)節(jié)點(diǎn).* 第2級 N1 N2* 第1級 N1 N2* 如果N1是本節(jié)點(diǎn),則 m_lpForwards[x] 保存的是N2* * [0] 就是原始鏈表.*/CNode* m_lpForwards[MAX_LEVEL];/**當(dāng)前節(jié)點(diǎn)的所在的最大索引級別*/int m_iMaxLevel;
};/*** @brief 跳表
*/
class CSkipList
{
public:CSkipList();~CSkipList();/*** @brief 查找指定的值的節(jié)點(diǎn)* @param v 正整數(shù)*/CNode* Find(int v);/*** @brief 插入指定的值* @param v 正整數(shù)*/void Insert(int v);/*** @brief 刪除指定的值的節(jié)點(diǎn)* @param v 正整數(shù)*/int Delete(int v);void PrintAll();/*** @brief 打印跳表結(jié)構(gòu)* @param l 等于-1時(shí)打印所有級別的結(jié)構(gòu) >=0時(shí)打印指定級別的結(jié)構(gòu)*/void PrintAll(int l);/*** @brief 插入節(jié)點(diǎn)時(shí),得到插入K級的隨機(jī)函數(shù)* @return K*/int RandomLevel();private:int levelCount;/*** 鏈表* 帶頭/哨所(節(jié)點(diǎn))*/CNode* m_lpHead;
};int main()
{CSkipList skipList;/// 插入原始值for(int i=1; i< 50; i++){if((i%3) == 0){skipList.Insert(i);}}for(int i=1; i< 50; i++){if((i%3) == 1){skipList.Insert(i);}}skipList.PrintAll();std::cout<<std::endl;// 打印所有等級結(jié)構(gòu)skipList.PrintAll(-1);// 查找std::cout<<std::endl;CNode* lpNode = skipList.Find(27);if(NULL != lpNode){std::cout<<"查找值為27的節(jié)點(diǎn),找到該節(jié)點(diǎn),節(jié)點(diǎn)值:"<<lpNode->GetData()<<std::endl;}else{std::cout<<"查找值為27的節(jié)點(diǎn),未找到該節(jié)點(diǎn)"<<std::endl;}/// 刪除std::cout<<std::endl;int ret = skipList.Delete(46);if(0 == ret){std::cout<<"查找值為46的節(jié)點(diǎn),找到該節(jié)點(diǎn),并刪除成功"<<std::endl;}else{std::cout<<"查找值為46的節(jié)點(diǎn),找到該節(jié)點(diǎn),刪除失敗"<<std::endl;}std::cout<<std::endl;//打印所有等級結(jié)構(gòu)skipList.PrintAll(-1);std::cin.ignore();return 0;
}CNode::CNode()
{m_data = -1;m_iMaxLevel = 0;for(int i=0; i<MAX_LEVEL; i++){m_lpForwards[i] = NULL;}
}
CNode::~CNode()
{}
CNode** CNode::GetIdxList()
{return m_lpForwards;
}void CNode::SetData(int v)
{m_data = v;
}
int CNode::GetData()
{return m_data;
}
void CNode::SetLevel(int l)
{m_iMaxLevel = l;
}
std::string CNode::toString()
{char tmp[32];std::string ret;ret.append("{ data: ");sprintf(tmp, "%d", m_data);ret.append(tmp);ret.append("; levels: ");sprintf(tmp, "%d", m_iMaxLevel);ret.append(tmp);ret.append(" }");return ret;
}CSkipList::CSkipList()
{levelCount = 1;m_lpHead = new CNode();
}
CSkipList::~CSkipList()
{}
CNode* CSkipList::Find(int v)
{CNode* lpNode = m_lpHead;/*** 從 最大級索引鏈表開始查找.* K -> k-1 -> k-2 ...->0*/for(int i=levelCount-1; i>=0; --i){/*** 查找小于v的節(jié)點(diǎn)(lpNode).*/while((NULL != lpNode->GetIdxList()[i]) && (lpNode->GetIdxList()[i]->GetData() < v)){lpNode = lpNode->GetIdxList()[i];}}/*** lpNode 是小于v的節(jié)點(diǎn), lpNode的下一個(gè)節(jié)點(diǎn)就等于或大于v的節(jié)點(diǎn)*/if((NULL != lpNode->GetIdxList()[0]) && (lpNode->GetIdxList()[0]->GetData() == v)){return lpNode->GetIdxList()[0];}return NULL;
}
void CSkipList::Insert(int v)
{/// 新節(jié)點(diǎn)CNode* lpNewNode = new CNode();if(NULL == lpNewNode){return;}/*** 新節(jié)點(diǎn)最大分布在的索引鏈表的上限* 如果返回 3,則 新的節(jié)點(diǎn)會在索引1、2、3上的鏈表都存在*/int level = RandomLevel();lpNewNode->SetData(v);lpNewNode->SetLevel(level);/*** 臨時(shí)索引鏈表* 主要是得到新的節(jié)點(diǎn)在每個(gè)索引鏈表上的位置*/CNode *lpUpdateNode[level];for(int i=0; i<level; i++){/// 每個(gè)索引鏈表的頭節(jié)點(diǎn)lpUpdateNode[i] =m_lpHead;}CNode* lpFind = m_lpHead;for(int i= level-1; i >= 0; --i){/*** 查找位置*   eg.  第1級  1  7  10*   如果插入的是 6*   lpFind->GetIdxList()[i]->GetData() : 表示節(jié)點(diǎn)lpFind在第1級索引的下一個(gè)節(jié)點(diǎn)的數(shù)據(jù)*   當(dāng) "lpFind->GetIdxList()[i]->GetData() < v"不成立的時(shí)候,*   新節(jié)點(diǎn)就要插入到 lpFind節(jié)點(diǎn)的后面, lpFind->GetIdxList()[i] 節(jié)點(diǎn)的前面*   即在這里 lpFind就是1  lpFind->GetIdxList()[i] 就是7*/while((NULL != lpFind->GetIdxList()[i]) && (lpFind->GetIdxList()[i]->GetData() < v)){lpFind = lpFind->GetIdxList()[i];}/// lpFind 是新節(jié)點(diǎn)在 第i級索引鏈表的后一個(gè)節(jié)點(diǎn)lpUpdateNode[i] = lpFind;}for(int i=0; i<level; ++i){/*** 重新設(shè)置鏈表指針位置*   eg  第1級索引 1  7  10*      插入6.*      lpUpdateNode[i] 節(jié)點(diǎn)是1; lpUpdateNode[i]->GetIdxList()[i]節(jié)點(diǎn)是7*  *  這2句代碼就是 把6放在 1和7之間*/lpNewNode->GetIdxList()[i] = lpUpdateNode[i]->GetIdxList()[i];lpUpdateNode[i]->GetIdxList()[i] = lpNewNode;}if(levelCount < level){levelCount = level;}
}
int CSkipList::Delete(int v)
{int ret = -1;CNode *lpUpdateNode[levelCount];CNode *lpFind = m_lpHead;for(int i=levelCount-1; i>= 0; --i){/*** 查找小于v的節(jié)點(diǎn)(lpFind).*/while((NULL != lpFind->GetIdxList()[i]) && (lpFind->GetIdxList()[i]->GetData() < v)){lpFind = lpFind->GetIdxList()[i];}lpUpdateNode[i] = lpFind;}/*** lpFind 是小于v的節(jié)點(diǎn), lpFind的下一個(gè)節(jié)點(diǎn)就等于或大于v的節(jié)點(diǎn)*/if((NULL != lpFind->GetIdxList()[0]) && (lpFind->GetIdxList()[0]->GetData() == v)){for(int i=levelCount-1; i>=0; --i){if((NULL != lpUpdateNode[i]->GetIdxList()[i]) && (v == lpUpdateNode[i]->GetIdxList()[i]->GetData())){lpUpdateNode[i]->GetIdxList()[i] = lpUpdateNode[i]->GetIdxList()[i]->GetIdxList()[i];ret = 0;}}}return ret;
}
void CSkipList::PrintAll()
{CNode* lpNode = m_lpHead;while(NULL != lpNode->GetIdxList()[0]){std::cout<<lpNode->GetIdxList()[0]->toString().data()<<std::endl;lpNode = lpNode->GetIdxList()[0];}
}
void CSkipList::PrintAll(int l)
{for(int i=MAX_LEVEL-1; i>=0;--i){CNode* lpNode = m_lpHead;std::cout<<"第"<<i<<"級:"<<std::endl;if((l < 0) || ((l >= 0) && (l == i))){while(NULL != lpNode->GetIdxList()[i]){std::cout<<lpNode->GetIdxList()[i]->GetData()<<" ";lpNode = lpNode->GetIdxList()[i];}std::cout<<std::endl;if(l >= 0){break;}}}
}
int GetRandom()
{static int _count = 1;std::default_random_engine generator(time(0) + _count);std::uniform_int_distribution<int> distribution(1,99999/*0x7FFFFFFF*/);int dice_roll = distribution(generator);_count += 100;return dice_roll;
}
int CSkipList::RandomLevel()
{int level = 1;for(int i=1; i<MAX_LEVEL; ++i){if(1 == (GetRandom()%3)){level++;}}return level;
}

總結(jié)

以上是生活随笔為你收集整理的skiplist跳表的 实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。