近期學(xué)習(xí)了一些底層的知識(shí)，但是代碼方面觸碰的很少。為了能落實(shí)到實(shí)處，我把之前一直拖著的LevelDB源碼搬了出來(lái)，詳細(xì)地分析了一下其跳表部分(SkipList)。
https://github.com/google/leveldb/blob/master/doc/index.md
上面的鏈接是LevelDB的GitHub源碼位置，大家可以下載后比對(duì)進(jìn)行學(xué)習(xí)。
為了能夠加速學(xué)習(xí)的效率，起初我準(zhǔn)備參考已經(jīng)完成的blog來(lái)進(jìn)行分析。后來(lái)發(fā)現(xiàn)，他們的解析雖然很多，但是都不太細(xì)致，也不系統(tǒng)。于是我在自己的理解基礎(chǔ)上準(zhǔn)備對(duì)這個(gè)跳表進(jìn)行一下詳細(xì)的分析。因?yàn)槲以趯W(xué)習(xí)的過(guò)程中遇到了很多疑惑，通過(guò)查閱以及揣摩得到了答案，所以我更清楚代碼中的核心問(wèn)題。在此我將逐代碼進(jìn)行分析，并在后續(xù)慢慢補(bǔ)充代碼中存在的知識(shí)點(diǎn)。
希望本文能為讀者帶來(lái)一些收獲！
前言
本文同樣更新在私人公眾號(hào)上，在此推廣一下歡迎大家關(guān)注：
公眾號(hào)會(huì)定期更新一些計(jì)算機(jī)系統(tǒng)的底層知識(shí)，爭(zhēng)取以最細(xì)節(jié)、最簡(jiǎn)潔的方式幫助讀者理解系統(tǒng)的一些知識(shí)。
SkipList背景知識(shí)
skiplist 由William Pugh 在論文Skip Lists: A Probabilistic Alternative to Balanced Trees 中提出的一種數(shù)據(jù)結(jié)構(gòu)，skiplist 是一種隨機(jī)化存儲(chǔ)的多層線性鏈表結(jié)構(gòu)，插入，查找，刪除的都是對(duì)數(shù)級(jí)別的時(shí)間復(fù)雜度。skiplist 和平衡樹(shù)有相同的時(shí)間復(fù)雜度，但相比平衡樹(shù)，skip實(shí)現(xiàn)起來(lái)更簡(jiǎn)單。
一個(gè)高度為4的skiplist如下圖所示：
從垂直角度看，skiplist 的第0層（最下面一層）以單鏈表的形式按照從小到大的順序存儲(chǔ)全部數(shù)據(jù)，越高層的鏈表的節(jié)點(diǎn)數(shù)越少，高層的節(jié)點(diǎn)用于索引的作用，通過(guò)最高層不斷索引到第0層從而獲得節(jié)點(diǎn)。通過(guò)在高層較少的節(jié)點(diǎn)中查找就可以確定需要定位的位置處于哪個(gè)區(qū)間，從高層到低層不斷縮小查找區(qū)間。
LevelDB代碼
為了簡(jiǎn)化我們的分析，我們分模塊對(duì)代碼進(jìn)行講解：
Skiplist-節(jié)點(diǎn)結(jié)構(gòu)體
?
首先我們先講述一下代碼中Skiplist的結(jié)構(gòu)體與Class類：
template <typename Key, class Comparator>
struct SkipList<Key, Comparator>::Node {
explicit Node(const Key& k) : key(k) {}
?
Key const key;
?
// Accessors/mutators for links. Wrapped in methods so we can
// add the appropriate barriers as necessary.
// 加載Next節(jié)點(diǎn)
Node* Next(int n) {
assert(n >= 0);
// Use an 'acquire load' so that we observe a fully initialized
// version of the returned Node.
return next_[n].load(std::memory_order_acquire);
}
void SetNext(int n, Node* x) {
assert(n >= 0);
// Use a 'release store' so that anybody who reads through this
// pointer observes a fully initialized version of the inserted node.
next_[n].store(x, std::memory_order_release);
}
?
// No-barrier variants that can be safely used in a few locations.
Node* NoBarrier_Next(int n) {
assert(n >= 0);
return next_[n].load(std::memory_order_relaxed);
}
void NoBarrier_SetNext(int n, Node* x) {
assert(n >= 0);
next_[n].store(x, std::memory_order_relaxed);
}
?
private:
// Array of length equal to the node height. next_[0] is lowest level link.
std::atomic<Node*> next_[1];
};
上述代碼為L(zhǎng)evelDB中的Node結(jié)構(gòu)，而Node代表跳表中的結(jié)點(diǎn)（key：value對(duì)）。
其中該結(jié)構(gòu)體中包括兩個(gè)私有變量：當(dāng)前節(jié)點(diǎn)的Key值以及當(dāng)前Node指向的下一個(gè)結(jié)構(gòu)體next_[1]（其中存儲(chǔ)的是某一層中大于等于該節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)Node，所以只有1即可）。
結(jié)構(gòu)體包含了四個(gè)方法Next、SetNext、NoBarrier_Next、NoBarrier_SetNext。前兩個(gè)方法對(duì)應(yīng)加載與讀取（內(nèi)存使用barrier按需進(jìn)行），后兩個(gè)方案對(duì)應(yīng)非屏障方案（可以亂序執(zhí)行）加載與讀取。這四種方案均對(duì)next_[1]進(jìn)行操作。Node結(jié)構(gòu)圖如下所示。
后續(xù)我們專門對(duì)內(nèi)存屏障做一些分享。
LevelDB中跳表的工具類
class Iterator {
public:
// Initialize an iterator over the specified list.
// The returned iterator is not valid.
explicit Iterator(const SkipList* list);
?
// Returns true iff the iterator is positioned at a valid node.
bool Valid() const;
?
// Returns the key at the current position.
// REQUIRES: Valid()
const Key& key() const;
?
// Advances to the next position.
// REQUIRES: Valid()
void Next();
?
// Advances to the previous position.
// REQUIRES: Valid()
void Prev();
?
// Advance to the first entry with a key >= target
void Seek(const Key& target);
?
// Position at the first entry in list.
// Final state of iterator is Valid() iff list is not empty.
void SeekToFirst();
?
// Position at the last entry in list.
// Final state of iterator is Valid() iff list is not empty.
void SeekToLast();
?
private:
const SkipList* list_;
Node* node_;
// Intentionally copyable
};
其中包括了7public個(gè)函數(shù)以及2個(gè)私有成員變量。
而工具類隸屬于SkipList類中，并且在SkipList中同樣有Node成員、kMaxHeight（level最高高度）、以及插入函數(shù)Insert()、包含函數(shù)Contains()、隨機(jī)高度函數(shù)RandomHeight()、比較函數(shù)KeyIsAfterNode()以及三個(gè)搜索函數(shù)。
源碼為：
class SkipList {
下面我們針對(duì)跳表的關(guān)鍵函數(shù)進(jìn)行分析。
我們知道，對(duì)數(shù)據(jù)的操作包括最重要的四個(gè)步驟：增、刪、改、查。而LevelDB中的SkipList并沒(méi)有刪除、修改操作，所以我們這里重點(diǎn)Follow插入與查詢的過(guò)程。
我們首先在理論上分析一下跳表是如何插入數(shù)據(jù)的：
插入操作
我們來(lái)看一個(gè)插入數(shù)據(jù)的例子。
我們將key-value 存放在在內(nèi)存中采用的結(jié)構(gòu)是 skiplist。上圖分為4層結(jié)構(gòu)，由底部0到最上層3。
在上圖中插入 30：
先得到一個(gè)隨機(jī)值（ 1 到 kMaxHeight 之間）來(lái)設(shè)置 30 這個(gè)節(jié)點(diǎn)的層數(shù)，假設(shè)得到的是 5，定義一個(gè) prev[5]，用來(lái)存放這五層中30 的前一個(gè)節(jié)點(diǎn)。這里這個(gè)隨機(jī)數(shù) 5 意味著從第0層到第4層均會(huì)存儲(chǔ)30這個(gè)值；
上圖中也就 4 層，咋整？（skiplist 有兩個(gè)關(guān)于層數(shù)的變量，第一個(gè)是 kMaxHeight，表示允許的最大層；第二個(gè)是 max_height_，表示 skiplist 當(dāng)前最大層）；
沒(méi)事，將大于 4 的層以上的節(jié)點(diǎn)的 prev 全部指向 head_，也就是將 prev[4] = head_(數(shù)組第五個(gè)位置賦值為head_), 并將當(dāng)前最大層數(shù) max_height_ 設(shè)置為 5；
還是按照上面查詢的步驟，只不過(guò)把每次降一層時(shí)的節(jié)點(diǎn)放在 prev 中，那么；
prev[4] = head_(第5層);
說(shuō)白了，假設(shè)我們插入的值是x，如果我們隨機(jī)到的值是n，那么該數(shù)字在0~n-1層都會(huì)出現(xiàn)；****其中prev[]數(shù)組中存儲(chǔ)的值是每一層x所在位置的前一個(gè)數(shù)（<=所插入值的值）。
PS：（head ---> 0 ---> 1 ---> 2 ---> 4.......，如果x為3，那么這里prev存儲(chǔ)的就是2這個(gè)點(diǎn)）
得到 prev 后，我們要根據(jù)prev中的值來(lái)更新x中的內(nèi)容。
在x結(jié)點(diǎn)內(nèi)部存在私有變量next_[n]，這個(gè)私有變量存儲(chǔ)x在每一層的后續(xù)結(jié)點(diǎn)，例如下面圖中的7這個(gè)結(jié)點(diǎn)：
7這個(gè)節(jié)點(diǎn)中的next_[0]代表第0層的10；****next_[1]代表第一層的15；****next_[2]代表第二層的31；****next_[3]代表第三層的31；
了解了這些基本概念后，我們看代碼就會(huì)非常輕松：
void SkipList<Key, Comparator>::Insert(const Key& key) {
// TODO(opt): We can use a barrier-free variant of FindGreaterOrEqual()
// here since Insert() is externally synchronized.
Node* prev[kMaxHeight];
// 在prev數(shù)組中找到不小于key的數(shù) 根據(jù)函數(shù)，這里傳入指針的指針，即直接將prev[kMaxHeight]的值修改掉
Node* x = FindGreaterOrEqual(key, prev);
?
// Our data structure does not allow duplicate insertion
assert(x == nullptr || !Equal(key, x->key));
// 隨機(jī)化一個(gè)高度出來(lái)
int height = RandomHeight();
// 如果隨機(jī)出的高度 > 已有的高度
if (height > GetMaxHeight()) {
for (int i = GetMaxHeight(); i < height; i++) {
// 如果高度 > 當(dāng)前的高度，那么會(huì)將當(dāng)前高度之上的所有節(jié)點(diǎn)之上均初始化head節(jié)點(diǎn)
prev[i] = head_;
}
// It is ok to mutate max_height_ without any synchronization
// with concurrent readers. A concurrent reader that observes
// the new value of max_height_ will see either the old value of
// new level pointers from head_ (nullptr), or a new value set in
// the loop below. In the former case the reader will
// immediately drop to the next level since nullptr sorts after all
// keys. In the latter case the reader will use the new node.
?
//可以進(jìn)行并發(fā)操作，這個(gè)高度不沖突
max_height_.store(height, std::memory_order_relaxed);
}
?
x = NewNode(key, height);
for (int i = 0; i < height; i++) {
// NoBarrier_SetNext() suffices since we will add a barrier when
// we publish a pointer to "x" in prev[i].
?
// 在i層中的當(dāng)前x節(jié)點(diǎn)所指向的下一個(gè)節(jié)點(diǎn)為（prev[i]的下一個(gè)節(jié)點(diǎn)）
// —— 即將x插入到prev[i] 與 next_prev[i]之間
x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));
prev[i]->SetNext(i, x);
}
}
該流程分如下步驟：
1 首先初始化Node數(shù)組：
Node* prev[kMaxHeight];
2 調(diào)用函數(shù)FindGreaterOrEqal()與斷言機(jī)制，有兩個(gè)作用：首先是將prev[]數(shù)組賦初值（傳入的是引用，可以直接把prev改掉），之后獲取到x（>或者=key的值），并對(duì)x進(jìn)行判斷，如果相等則退出（只能找到>的值，而在list中不允許有相等的情況出現(xiàn)）
Node* x = FindGreaterOrEqual(key, prev);
3 隨機(jī)一個(gè)高度出來(lái)
int height = RandomHeight();
這里詳細(xì)擴(kuò)展一下這個(gè)隨機(jī)函數(shù)：
int height = RandomHeight();
這里詳細(xì)擴(kuò)展一下這個(gè)隨機(jī)函數(shù)：
// 得到一個(gè)隨機(jī)的高度
template<typename Key, class Comparator>
int SkipList<Key,Comparator>::RandomHeight() {
static const unsigned int kBranching = 4;
// 初始為 1
int height = 1;
// 得到一個(gè)隨機(jī)值，如果隨機(jī)值是 4 的倍數(shù)就返回 height，否則 keight 就加 1，為什么要這么做？
// 如果我們得到一個(gè)隨機(jī)值，直接對(duì) kMaxHeight 取模加 1，然后賦值給 height，那么 height 在 [1~12] 之前出現(xiàn)的概率一樣的
// 如果節(jié)點(diǎn)個(gè)數(shù)為 n，那么有 12 層的節(jié)點(diǎn)有 n/12 個(gè)，11 層的有 n/12+n/12(需要把12層的也加上)，
// 節(jié)點(diǎn)太多，最上層平均前進(jìn)一次才右移 12 個(gè)節(jié)點(diǎn)，下面層就更不用說(shuō)了，效率低；
// 作者的方法是每一層會(huì)按照4的倍數(shù)減少，出現(xiàn)4層的概率只有出現(xiàn)3層概率的1/4，這樣查詢起來(lái)效率是不是大大提升了呢
?
while (height < kMaxHeight && ((rnd_.Next() % kBranching) == 0)) {
height++;
}
assert(height > 0);
assert(height <= kMaxHeight);
return height;
}
- // 得到一個(gè)隨機(jī)值，如果隨機(jī)值是 4 的倍數(shù)就返回 height，否則 keight 就加 1，為什么要這么做？**
// 如果我們得到一個(gè)隨機(jī)值，直接對(duì) kMaxHeight 取模加 1，然后賦值給 height，那么 height 在 [1~12] 之前出現(xiàn)的概率一樣的**
// 如果節(jié)點(diǎn)個(gè)數(shù)為 n，那么有 12 層的節(jié)點(diǎn)有 n/12 個(gè)，11 層的有 n/12+n/12(需要把12層的也加上)，**
// 節(jié)點(diǎn)太多，最上層平均前進(jìn)一次才右移 12 個(gè)節(jié)點(diǎn)，下面層就更不用說(shuō)了，效率低；**
// 作者的方法是每一層會(huì)按照4的倍數(shù)減少，出現(xiàn)4層的概率只有出現(xiàn)3層概率的1/4，這樣查詢起來(lái)效率是不是大大提升了呢**
說(shuō)白了就是讓上層的數(shù)字不要太多，下層的可以多一些。呈現(xiàn)倒漏斗形狀。
4 之后如果當(dāng)前隨機(jī)到的高度比list中最大值要大（比如例子中本來(lái)只有4層，而我們插入30時(shí)隨機(jī)到了5），那么將多出來(lái)的層中的prev[]指向頭結(jié)點(diǎn)（因?yàn)楫?dāng)前層是新建的所以沒(méi)有其他結(jié)點(diǎn)emmmm）。
if (height > GetMaxHeight()) {
for (int i = GetMaxHeight(); i < height; i++) {
// 如果高度 > 當(dāng)前的高度，那么會(huì)將當(dāng)前高度之上的所有節(jié)點(diǎn)之上均初始化head節(jié)點(diǎn)
prev[i] = head_;
}
5 當(dāng)我們得到了prev[]數(shù)組，以及所需插入key的后面的結(jié)點(diǎn)x后（x>key），我們很順利進(jìn)行更新操作了！??！
for (int i = 0; i < height; i++) {
// NoBarrier_SetNext() suffices since we will add a barrier when
// we publish a pointer to "x" in prev[i].
// 在i層中的當(dāng)前x節(jié)點(diǎn)所指向的下一個(gè)節(jié)點(diǎn)為（prev[i]的下一個(gè)節(jié)點(diǎn)）
// —— 即將x插入到prev[i] 與 next_prev[i]之間
x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));
prev[i]->SetNext(i, x);
}
加入原始第0層結(jié)點(diǎn)為 head ——> 5 ——> 10 ——> 15 ——>20。此時(shí)我們需要插入一個(gè)結(jié)點(diǎn)18，那么prev[0]指向15，x為20。所以第5步得到更新：
head ——> 5 ——> 10 ——> 15 ——> 18 ——> 20
查詢操作
我們來(lái)看上述的結(jié)構(gòu)，從0到4共有五層，此時(shí)我們計(jì)劃查詢29。
- 首先 skiplist 有一個(gè)變量 head_ 始終指向第一個(gè)節(jié)點(diǎn)的最上層，也就是圖中最上層的 head_
- 29 和第 4 層 head_ 的 next 節(jié)點(diǎn) 7 比較，大于 7，此時(shí)頭節(jié)點(diǎn)指向第 4 層的 7
- 29 和第 4 層 7 的 next 節(jié)點(diǎn) 31 比較，小于 31，降一層
- 29 和第 3 層 7 的 next 節(jié)點(diǎn) 31 比較，小于 31，降一層
- 29 和第 2 層 7 的 next 節(jié)點(diǎn) 15 比較，大于 15，此時(shí)頭節(jié)點(diǎn)指向第 2 層的 15
- 29 和第 2 層 15 的 next 節(jié)點(diǎn) 31 比較，小于 31，降一層
- 29 和第 1 層 15 的 next 節(jié)點(diǎn) 24 比較，大于 24，此時(shí)頭節(jié)點(diǎn)指向第 1 層的 24
- 29 和第 1 層 24 的 next 節(jié)點(diǎn) 29 比較，等于 29，且是第一層，沒(méi)錯(cuò)就是你了
代碼中的查詢函數(shù)：
inline void SkipList<Key, Comparator>::Iterator::Seek(const Key& target) {
node_ = list_->FindGreaterOrEqual(target, nullptr);
}
而Seek指向了FindGreaterOrEqual()。
于是我們查看該函數(shù)：
// FindGreaterOrEqual 找到>或者=Key的節(jié)點(diǎn)，prev[]中存儲(chǔ)的內(nèi)容是每一層中比key小的數(shù)是哪個(gè)
template <typename Key, class Comparator>
typename SkipList<Key, Comparator>:
:Node*
SkipList<Key, Comparator>::FindGreaterOrEqual(const Key& key,
Node** prev) const {
Node* x = head_;
int level = GetMaxHeight() - 1;
while (true) {
// next指向的是x同層的下一個(gè)節(jié)點(diǎn)，可能為空
Node* next = x->Next(level);
// 如果key在next的后面，x指針指向next
if (KeyIsAfterNode(key, next)) {
// Keep searching in this list
x = next;
} else {
// 如果next為空或key在next的前面，
// 說(shuō)明要插入的key是要比當(dāng)前層的next節(jié)點(diǎn)小的即（head——>next，而key<next，所以放head與next中間）
// 此時(shí)要把當(dāng)前prev[level]存上head，即找到當(dāng)前層中比key小的點(diǎn)
// 即prev[level]中存的是各個(gè)層中比key小的點(diǎn)
if (prev != nullptr) prev[level] = x;
if (level == 0) {
// 層數(shù)為0的話，說(shuō)明兩個(gè)節(jié)點(diǎn)之間沒(méi)有挑過(guò)其他節(jié)點(diǎn)，
// 而此時(shí)next是大于或等于key的，key肯定是大于next的前一個(gè)節(jié)點(diǎn)的（不大于的話走不到next節(jié)點(diǎn)）
// 返回的next節(jié)點(diǎn)只能大于或等于key節(jié)點(diǎn)
return next;
} else {
// Switch to next list
level--;
}
}
}
}
該函數(shù)需要我們傳入需要查詢的key值以及用于存儲(chǔ)key在每一層的前一個(gè)數(shù)的prev[]數(shù)組。
1 首先該函數(shù)會(huì)初始化Node x，指向頭結(jié)點(diǎn)head
Node* x = head_;
2 之后進(jìn)入循環(huán)，該循環(huán)首先會(huì)從最頂層的level開(kāi)始向下延伸
Node* next = x->Next(level);
將next指向head后面的結(jié)點(diǎn)，并且一層一層向后指
3 尋找key>next的情況，不斷尋找指導(dǎo)找到緊鄰key前面的那個(gè)值
if (KeyIsAfterNode(key, next)) {
// Keep searching in this list
x = next;
}
4 如果結(jié)點(diǎn)next比key大（注意，這里的next是x的下一個(gè)節(jié)點(diǎn)，所以x還是要小于key的），那么就向下層走。
else {
// 如果next為空或key在next的前面，
// 說(shuō)明要插入的key是要比當(dāng)前層的next節(jié)點(diǎn)小的即（head——>next，而key<next，所以放head與next中間）
// 此時(shí)要把當(dāng)前prev[level]存上head，即找到當(dāng)前層中比key小的點(diǎn)
// 即prev[level]中存的是各個(gè)層中比key小的點(diǎn)
if (prev != nullptr) prev[level] = x;
if (level == 0) {
// 而此時(shí)next是大于或等于key的，key肯定是大于next的前一個(gè)節(jié)點(diǎn)的（不大于的話走不到next節(jié)點(diǎn)）
// 返回的next節(jié)點(diǎn)只能大于或等于key節(jié)點(diǎn)
return next;
} else {
// Switch to next list
level--;
}
}
當(dāng)搜索到最后一層時(shí)（第0層是數(shù)據(jù)最全的一層），此時(shí)如果遇到next>key的情況，那么就找到了正確的數(shù)據(jù)，我們就返回next即可。
其余工具函數(shù)解析
新建Node并分配空間的函數(shù)：
// 創(chuàng)建一個(gè)新的節(jié)點(diǎn)，而分配內(nèi)存為：節(jié)點(diǎn)結(jié)構(gòu)體大小+高度（每一層高度中均可以存一個(gè)Node）
template <typename Key, class Comparator>
typename SkipList<Key, Comparator>::Node* SkipList<Key, Comparator>::NewNode(
const Key& key, int height) {
char* const node_memory = arena_->AllocateAligned(
sizeof(Node) + sizeof(std::atomic<Node*>) * (height - 1));
return new (node_memory) Node(key);
}
該函數(shù)中傳入node的key值與樹(shù)的高度height，并且分配空間（sizeof(Node) + sizeof(std::atomic<Node*>) * (height - 1))）
即：Node數(shù)據(jù)結(jié)構(gòu)的大小+（height-1）個(gè)所需存儲(chǔ)的指向下一個(gè)Node的空間（每一層都需要指向下一個(gè)結(jié)點(diǎn)）
Valid()函數(shù)：
inline bool SkipList<Key, Comparator>::Iterator::Valid() const {
return node_ != nullptr;
}
檢測(cè)node是不是空。
Next函數(shù)與Prev函數(shù)：
template <typename Key, class Comparator>
inline void SkipList<Key, Comparator>::Iterator::Next() {
assert(Valid());
// Node結(jié)構(gòu)體的私有變量，用于在level 0層中查找比他大的key
node_ = node_->Next(0);
}
?
template <typename Key, class Comparator>
inline void SkipList<Key, Comparator>::Iterator::Prev() {
// Instead of using explicit "prev" links, we just search for the
// last node that falls before key.
assert(Valid());
node_ = list_->FindLessThan(node_->key);
if (node_ == list_->head_) {
node_ = nullptr;
}
}
使用node結(jié)構(gòu)體中存儲(chǔ)的第0層的私有變量導(dǎo)出大于他的數(shù)（Next(0)）
而找小于key的數(shù)需要調(diào)用下面的函數(shù)：
template <typename Key, class Comparator>
typename SkipList<Key, Comparator>::Node*
SkipList<Key, Comparator>::FindLessThan(const Key& key) const {
Node* x = head_;
int level = GetMaxHeight() - 1;
while (true) {
// 條件返回錯(cuò)誤，則終止程序執(zhí)行。即必須滿足當(dāng)前x節(jié)點(diǎn)是頭節(jié)點(diǎn) 或者 x的值比傳入的key要小
assert(x == head_ || compare_(x->key, key) < 0);
Node* next = x->Next(level);
// 如果發(fā)現(xiàn)x的next的值比key要大或者與key相等，則將x返回
if (next == nullptr || compare_(next->key, key) >= 0) {
if (level == 0) {
return x;
} else {
// Switch to next list
level--;
}
} else {
x = next;
}
}
}
LevelDB中的跳表最核心的函數(shù)基本上分析完成了，其實(shí)最難理解的還是那個(gè)跳表Node的結(jié)構(gòu)體，只要理解了他里面存儲(chǔ)是是key以及多個(gè)level中的next結(jié)點(diǎn)。其中他在結(jié)構(gòu)體代碼中寫到：
// Array of length equal to the node height. next_[0] is lowest level link.
std::atomic<Node*> next_[1];
總結(jié)
這個(gè)next_[1]應(yīng)該是個(gè)變長(zhǎng)的數(shù)組，里面存儲(chǔ)的結(jié)點(diǎn)長(zhǎng)度是level的高度。所以這個(gè)1在這里代表的不是長(zhǎng)度為1的意思。需要我們注意一下。
希望本文能為大家?guī)?lái)一些啟發(fā)，后期會(huì)針對(duì)levelDB中的并發(fā)訪問(wèn)以及內(nèi)存屏障等內(nèi)容進(jìn)行深入探討，歡迎大家繼續(xù)閱讀。
本文記錄非常詳細(xì)，就是為了彌補(bǔ)很多博客不注重細(xì)節(jié)的問(wèn)題，所以讀起來(lái)有可能會(huì)相對(duì)慢一些，但大家順序讀下來(lái)肯定會(huì)有很多收獲的，感謝。
也感謝https://blog.csdn.net/xuxuan_csd/article/details/72965674博客，為了更清晰的解釋我也使用了其中部分解析例子。
轉(zhuǎn)載請(qǐng)標(biāo)注來(lái)源哦！可以搜索微信公眾號(hào) ：“計(jì)算機(jī)系統(tǒng)知識(shí)分享站” 來(lái)加關(guān)注。
