redis使用跳躍表而不是樹(shù)的原因解析
Redis中支持五種數(shù)據(jù)類(lèi)型中有序集合Sorted Set的底層數(shù)據(jù)結(jié)構(gòu)使用的跳躍表，為何不使用其他的如平衡二叉樹(shù)、b+樹(shù)等數(shù)據(jù)結(jié)構(gòu)呢？
1，redis的設(shè)計(jì)目標(biāo)、性能需求：
redis是高性能的非關(guān)系型（NoSQL）內(nèi)存鍵值數(shù)據(jù)庫(kù)，它以其快速的操作速度而聞名。
讀取速度：Redis能實(shí)現(xiàn)極高的讀取速度，據(jù)官方測(cè)試報(bào)告，可以達(dá)到每秒約110,000次讀取操作。
寫(xiě)入速度：與讀取相比，寫(xiě)入速度略低，但仍然相當(dāng)可觀，官方數(shù)據(jù)顯示，Redis的寫(xiě)入速度大約是每秒81,000次操作。
類(lèi)似產(chǎn)品如Memcached等，無(wú)法達(dá)到如此性能。
2，有序集合都可以借助什么數(shù)據(jù)結(jié)構(gòu)及其基本原理
有序集合需求：自然有序，查找高速，支持范圍查找
2.1，傳統(tǒng)數(shù)組/鏈表+排序
數(shù)組或鏈表可以存儲(chǔ)數(shù)據(jù)，可以新增或修改數(shù)據(jù)后重新排序，
而在集合排序方面，最快的歸并排序也需要O(NlongN)的時(shí)間復(fù)雜度。
時(shí)間不夠快，但實(shí)現(xiàn)、使用方面簡(jiǎn)單
2.2，跳躍表（鏈表的優(yōu)化–鏈表+多級(jí)索引）
跳躍表最早是由William Pugh在1990年提出的，被用來(lái)代替平衡樹(shù)（如AVL樹(shù)和紅黑樹(shù)）來(lái)實(shí)現(xiàn)有序集合。跳躍表的查詢復(fù)雜度為O(log n)，與平衡樹(shù)相當(dāng)，但由于其實(shí)現(xiàn)較為簡(jiǎn)單，所以在實(shí)際使用中比平衡樹(shù)更加高效。
例：查找90
增加指針，讓指針指向遠(yuǎn)處個(gè)節(jié)點(diǎn)，
如上圖，共四層，最底層（原鏈表L1）節(jié)點(diǎn)是10 - 20 - 30 -… - 120，中間層L2增加節(jié)點(diǎn)10 - 30 - 40 - 60 - 80 - 100 - 120，L2上層L3增加節(jié)點(diǎn)10 - 40 - 80 - 120 最高層10 - 120
這樣形成三個(gè)新的鏈表，但它包含的節(jié)點(diǎn)個(gè)數(shù)只有原來(lái)的一部分；
當(dāng)我們查找數(shù)據(jù)之時(shí)，先沿著這個(gè)最高層鏈表進(jìn)行查找。當(dāng)碰到比待查數(shù)據(jù)大的節(jié)點(diǎn)時(shí)，再到中間層，最后回到原來(lái)的鏈表中進(jìn)行查找。
如查找90，共經(jīng)歷6步。
過(guò)程類(lèi)似二分查找，時(shí)間復(fù)雜度支持平均O(logN)，最壞O(N)的節(jié)點(diǎn)查找，還可以順序性操作來(lái)批量處理節(jié)點(diǎn)。
2.3，平衡二叉樹(shù)/紅黑樹(shù)
平衡二叉樹(shù)的查詢復(fù)雜度為O(logN)，但新增、刪除需要調(diào)整保持平衡，實(shí)現(xiàn)相對(duì)復(fù)雜；
范圍查詢方面，平衡二叉樹(shù)支持范圍查詢,但是這這種數(shù)據(jù)結(jié)構(gòu)要范圍查找要往回找,即回溯到父結(jié)點(diǎn),而B(niǎo)+樹(shù)的葉子結(jié)點(diǎn)的指針的效率則更高
2.4，B+樹(shù)
B+ Tree是一種經(jīng)典的多路平衡查找樹(shù)，它通常被用來(lái)實(shí)現(xiàn)磁盤(pán)上的數(shù)據(jù)結(jié)構(gòu)。在B+ Tree中，每個(gè)節(jié)點(diǎn)可以包含多個(gè)鍵值對(duì)，而且所有葉子節(jié)點(diǎn)都被連接成一個(gè)鏈表。B+ Tree的查詢復(fù)雜度也是O(log n)，但由于其實(shí)現(xiàn)較為復(fù)雜，所以在實(shí)際使用中通常用于數(shù)據(jù)庫(kù)系統(tǒng)等需要高效讀寫(xiě)的場(chǎng)景中。
3，跳躍表與平衡樹(shù)的實(shí)現(xiàn)
//redis源碼中跳躍表結(jié)構(gòu)的實(shí)現(xiàn)：
/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
sds ele;
double score;//分值
struct zskiplistNode *backward;//后退指針
//層
struct zskiplistLevel {
struct zskiplistNode *forward;//前進(jìn)指針
unsigned long span;//跨度
} level[];
} zskiplistNode;如圖，一個(gè)跳表節(jié)點(diǎn)，有l(wèi)evel數(shù)組，每個(gè)元素都有一個(gè)指向其他節(jié)點(diǎn)的指針，可以通過(guò)這些層來(lái)加快訪問(wèn)速度
3.1使用java實(shí)現(xiàn)跳躍表：
import java.util.Random;
class Node {
int key;
int value;
Node[] next;
public Node(int level, int key, int value) {
this.key = key;
this.value = value;
this.next = new Node[level + 1];
}
}
public class SkipList {
private static final int MAX_LEVEL = 16; // 最大層數(shù)
private int level; // 當(dāng)前層數(shù)
private Node head; // 頭節(jié)點(diǎn)
private Random random; // 用于生成隨機(jī)層數(shù)
public SkipList() {
this.level = 0;
this.head = new Node(MAX_LEVEL, 0, 0);
this.random = new Random();
}
// 生成隨機(jī)層數(shù)
private int randomLevel() {
int level = 0;
while (level < MAX_LEVEL && random.nextDouble() < 0.5) {
level++;
}
return level;
}
// 插入節(jié)點(diǎn)
public void insert(int key, int value) {
Node[] update = new Node[MAX_LEVEL + 1];
Node current = head;
for (int i = level; i >= 0; i--) {
while (current.next[i] != null && current.next[i].key < key) {
current = current.next[i];
}
update[i] = current;
}
int newLevel = randomLevel();
if (newLevel > level) {
for (int i = level + 1; i <= newLevel; i++) {
update[i] = head;
}
level = newLevel;
}
Node newNode = new Node(newLevel, key, value);
for (int i = 0; i <= newLevel; i++) {
newNode.next[i] = update[i].next[i];
update[i].next[i] = newNode;
}
}
// 查找節(jié)點(diǎn)
public Node search(int key) {
Node current = head;
for (int i = level; i >= 0; i--) {
while (current.next[i] != null && current.next[i].key < key) {
current = current.next[i];
}
}
if (current.next[0] != null && current.next[0].key == key) {
return current.next[0];
}
return null;
}
// 刪除節(jié)點(diǎn)
public void delete(int key) {
Node[] update = new Node[MAX_LEVEL + 1];
Node current = head;
for (int i = level; i >= 0; i--) {
while (current.next[i] != null && current.next[i].key < key) {
current = current.next[i];
}
update[i] = current;
}
if (current.next[0] != null && current.next[0].key == key) {
for (int i = 0; i <= level; i++) {
if (update[i].next[i] != current.next[i]) {
break;
}
update[i].next[i] = current.next[i];
}
while (level > 0 && head.next[level] == null) {
level--;
}
}
}
// 打印跳躍表
public void printSkipList() {
for (int i = level; i >= 0; i--) {
Node current = head;
System.out.print("Level " + i + ": ");
while (current.next[i] != null) {
System.out.print(current.next[i].key + " ");
current = current.next[i];
}
System.out.println();
}
}
public static void main(String[] args) {
SkipList skipList = new SkipList();
skipList.insert(3, 30);
skipList.insert(1, 10);
skipList.insert(2, 20);
skipList.insert(4, 40);
System.out.println("Skip List after insertion:");
skipList.printSkipList();
int searchKey = 2;
Node searchResult = skipList.search(searchKey);
if (searchResult != null) {
System.out.println("Node with key " + searchKey + " found. Value: " + searchResult.value);
} else {
System.out.println("Node with key " + searchKey + " not found.");
}
int deleteKey = 2;
skipList.delete(deleteKey);
System.out.println("Skip List after deletion of key " + deleteKey + ":");
skipList.printSkipList();
}
}3.2使用java實(shí)現(xiàn)平衡二叉樹(shù)（AVLTree）：
class Node {
int key, height;
Node left, right;
public Node(int key) {
this.key = key;
this.height = 1;
}
}
public class AVLTree {
private Node root;
// 獲取節(jié)點(diǎn)的高度
private int height(Node node) {
return (node == null) ? 0 : node.height;
}
// 獲取樹(shù)的平衡因子
private int getBalance(Node node) {
return (node == null) ? 0 : height(node.left) - height(node.right);
}
// 更新節(jié)點(diǎn)的高度
private void updateHeight(Node node) {
node.height = 1 + Math.max(height(node.left), height(node.right));
}
// 執(zhí)行右旋轉(zhuǎn)
private Node rightRotate(Node y) {
Node x = y.left;
Node T2 = x.right;
// 執(zhí)行旋轉(zhuǎn)
x.right = y;
y.left = T2;
// 更新高度
updateHeight(y);
updateHeight(x);
return x;
}
// 執(zhí)行左旋轉(zhuǎn)
private Node leftRotate(Node x) {
Node y = x.right;
Node T2 = y.left;
// 執(zhí)行旋轉(zhuǎn)
y.left = x;
x.right = T2;
// 更新高度
updateHeight(x);
updateHeight(y);
return y;
}
// 插入節(jié)點(diǎn)
public Node insert(Node node, int key) {
if (node == null) {
return new Node(key);
}
// 執(zhí)行標(biāo)準(zhǔn)的BST插入
if (key < node.key) {
node.left = insert(node.left, key);
} else if (key > node.key) {
node.right = insert(node.right, key);
} else {
// 相等的鍵不允許插入
return node;
}
// 更新節(jié)點(diǎn)的高度
updateHeight(node);
// 獲取平衡因子
int balance = getBalance(node);
// 進(jìn)行平衡操作
// 左重，需要右旋轉(zhuǎn)
if (balance > 1 && key < node.left.key) {
return rightRotate(node);
}
// 右重，需要左旋轉(zhuǎn)
if (balance < -1 && key > node.right.key) {
return leftRotate(node);
}
// 左右，先左旋轉(zhuǎn)后右旋轉(zhuǎn)
if (balance > 1 && key > node.left.key) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
// 右左，先右旋轉(zhuǎn)后左旋轉(zhuǎn)
if (balance < -1 && key < node.right.key) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
// 不需要平衡操作，直接返回節(jié)點(diǎn)
return node;
}
// 插入節(jié)點(diǎn)的公共接口
public void insert(int key) {
root = insert(root, key);
}
// 打印中序遍歷結(jié)果
private void inOrderTraversal(Node node) {
if (node != null) {
inOrderTraversal(node.left);
System.out.print(node.key + " ");
inOrderTraversal(node.right);
}
}
// 打印中序遍歷結(jié)果的公共接口
public void inOrderTraversal() {
inOrderTraversal(root);
System.out.println();
}
public static void main(String[] args) {
AVLTree avlTree = new AVLTree();
// 插入節(jié)點(diǎn)
avlTree.insert(10);
avlTree.insert(20);
avlTree.insert(30);
avlTree.insert(15);
avlTree.insert(5);
// 打印中序遍歷結(jié)果
System.out.println("Inorder traversal of the AVL tree:");
avlTree.inOrderTraversal();
}
}3.3java實(shí)現(xiàn)B+樹(shù)：
import java.util.ArrayList;
import java.util.List;
class BPlusTree {
private BPlusNode root;
private int order;
public BPlusTree(int order) {
this.root = new BPlusLeafNode();
this.order = order;
}
public void insert(int key, String value) {
root = root.insert(key, value);
}
public String search(int key) {
return root.search(key);
}
public void printTree() {
root.print();
}
// B+樹(shù)節(jié)點(diǎn)抽象類(lèi)
abstract static class BPlusNode {
List<Integer> keys;
BPlusNode() {
this.keys = new ArrayList<>();
}
abstract BPlusNode insert(int key, String value);
abstract String search(int key);
abstract void print();
}
// B+樹(shù)葉子節(jié)點(diǎn)類(lèi)
static class BPlusLeafNode extends BPlusNode {
List<String> values;
BPlusLeafNode next; // 用于連接葉子節(jié)點(diǎn)形成鏈表
BPlusLeafNode() {
this.values = new ArrayList<>();
this.next = null;
}
@Override
BPlusNode insert(int key, String value) {
int index = 0;
while (index < keys.size() && keys.get(index) < key) {
index++;
}
keys.add(index, key);
values.add(index, value);
// 檢查是否需要分裂
if (keys.size() > order) {
int splitIndex = keys.size() / 2;
BPlusLeafNode newLeaf = new BPlusLeafNode();
// 將一半的鍵和值移至新節(jié)點(diǎn)
newLeaf.keys.addAll(keys.subList(splitIndex, keys.size()));
newLeaf.values.addAll(values.subList(splitIndex, values.size()));
keys.subList(splitIndex, keys.size()).clear();
values.subList(splitIndex, values.size()).clear();
// 調(diào)整葉子節(jié)點(diǎn)鏈表
newLeaf.next = next;
next = newLeaf;
return newLeaf;
}
return this;
}
@Override
String search(int key) {
int index = 0;
while (index < keys.size() && keys.get(index) <= key) {
if (keys.get(index) == key) {
return values.get(index);
}
index++;
}
return null;
}
@Override
void print() {
System.out.print("Leaf Node: ");
for (int i = 0; i < keys.size(); i++) {
System.out.print("(" + keys.get(i) + ", " + values.get(i) + ") ");
}
System.out.println();
}
}
// B+樹(shù)內(nèi)部節(jié)點(diǎn)類(lèi)
static class BPlusInternalNode extends BPlusNode {
List<BPlusNode> children;
BPlusInternalNode() {
this.children = new ArrayList<>();
}
@Override
BPlusNode insert(int key, String value) {
int index = 0;
while (index < keys.size() && keys.get(index) < key) {
index++;
}
BPlusNode child = children.get(index);
BPlusNode newChild = child.insert(key, value);
if (newChild != child) {
keys.add(index, newChild.keys.get(0));
children.add(index + 1, newChild);
if (keys.size() > order) {
int splitIndex = keys.size() / 2;
BPlusInternalNode newInternal = new BPlusInternalNode();
// 將一半的鍵和子節(jié)點(diǎn)移至新節(jié)點(diǎn)
newInternal.keys.addAll(keys.subList(splitIndex, keys.size()));
newInternal.children.addAll(children.subList(splitIndex + 1, children.size()));
keys.subList(splitIndex, keys.size()).clear();
children.subList(splitIndex + 1, children.size()).clear();
return newInternal;
}
}
return this;
}
@Override
String search(int key) {
int index = 0;
while (index < keys.size() && keys.get(index) <= key) {
index++;
}
return children.get(index).search(key);
}
@Override
void print() {
System.out.print("Internal Node: ");
for (int i = 0; i < keys.size(); i++) {
System.out.print(keys.get(i) + " ");
}
System.out.println();
for (BPlusNode child : children) {
child.print();
}
}
}
public static void main(String[] args) {
BPlusTree bPlusTree = new BPlusTree(3);
bPlusTree.insert(10, "Value10");
bPlusTree.insert(20, "Value20");
bPlusTree.insert(5, "Value5");
bPlusTree.insert(6, "Value6");
bPlusTree.insert(12, "Value12");
bPlusTree.insert(30, "Value30");
System.out.println("B+ Tree after insertion:");
bPlusTree.printTree();
int searchKey = 12;
String searchResult = bPlusTree.search(searchKey);
if (searchResult != null) {
System.out.println("Value for key " + searchKey + ": " + searchResult);
} else {
System.out.println("Key " + searchKey + " not found.");
}
}
}4，Redis的作者 @antirez 的原話與總結(jié)
There are a few reasons:
1、They are not very memory intensive. It’s up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.
2、A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.
3、They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.
主要是從內(nèi)存占用、對(duì)范圍查找的支持、實(shí)現(xiàn)難易程度這三方面總結(jié)的原因，
簡(jiǎn)單翻譯一下：
1、它們不是非常內(nèi)存密集型的?；旧嫌赡銢Q定。改變關(guān)于節(jié)點(diǎn)具有給定級(jí)別數(shù)的概率的參數(shù)將使其比 btree 占用更少的內(nèi)存。
2、Zset 經(jīng)常需要執(zhí)行 ZRANGE 或 ZREVRANGE 的命令，即作為鏈表遍歷跳表。通過(guò)此操作，跳表的緩存局部性至少與其他類(lèi)型的平衡樹(shù)一樣好。
3、它們更易于實(shí)現(xiàn)、調(diào)試等。例如，由于跳表的簡(jiǎn)單性，我收到了一個(gè)補(bǔ)?。ㄒ呀?jīng)在Redis master中），其中擴(kuò)展了跳表，在 O(log(N) 中實(shí)現(xiàn)了 ZRANK。它只需要對(duì)代碼進(jìn)行少量修改。
跳躍表的優(yōu)勢(shì)：
1，時(shí)間復(fù)雜度方面：大部分情況下，跳躍表的效率和平衡樹(shù)媲美；
2，算法實(shí)現(xiàn)方面：跳躍表的實(shí)現(xiàn)比平衡樹(shù)、b+樹(shù)更為簡(jiǎn)單；
3，范圍查找方面，跳表比平衡樹(shù)操作要簡(jiǎn)單，平衡樹(shù)需要回溯到父結(jié)點(diǎn)，條表可以做到 O(logn) 的時(shí)間復(fù)雜度定位區(qū)間的起點(diǎn)，然后在原始鏈表中順序往后遍歷；
4，對(duì)于小數(shù)據(jù)集的性能： 在某些場(chǎng)景下，跳表在小數(shù)據(jù)集上的性能可能優(yōu)于B+樹(shù)。跳表的查詢操作在某些情況下可能更迅速。
到此這篇關(guān)于redis使用跳躍表而不是樹(shù)的原因解析的文章就介紹到這了,更多相關(guān)redis為什么使用跳躍表而不是樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Redis實(shí)現(xiàn)分布式鎖的幾種方法總結(jié)
這篇文章主要介紹了Redis實(shí)現(xiàn)分布式鎖的幾種方法總結(jié)的相關(guān)資料, Redis實(shí)現(xiàn)與Zookeeper實(shí)現(xiàn)和數(shù)據(jù)庫(kù)實(shí)現(xiàn)，需要的朋友可以參考下2017-07-07
在Centos?8.0中安裝Redis服務(wù)器的教程詳解
由于考慮到linux服務(wù)器的性能，所以經(jīng)常需要把一些中間件安裝在linux服務(wù)上，今天通過(guò)本文給大家介紹下在Centos?8.0中安裝Redis服務(wù)器的詳細(xì)過(guò)程，感興趣的朋友一起看看吧2022-03-03
本文介紹了Redis集群全量數(shù)據(jù)清理的操作流程,包括檢查數(shù)據(jù)、腳本清理步驟、結(jié)果確認(rèn)及注意事項(xiàng),建議在低峰期進(jìn)行并備份數(shù)據(jù),確保上線環(huán)境干凈,需要的朋友可以參考下2025-10-10
大家好，本篇文章主要講的是搭建Redis服務(wù)器步驟詳細(xì)介紹，感興趣的同學(xué)趕快來(lái)看一看吧，對(duì)你有幫助的話記得收藏一下，方便下次瀏覽2021-12-12
淺析Redis中紅鎖RedLock的實(shí)現(xiàn)原理
RedLock?是一種分布式鎖的實(shí)現(xiàn)算法,由?Redis?的作者?Salvatore?Sanfilippo（也稱(chēng)為?Antirez）提出,本文主要為大家詳細(xì)介紹了紅鎖RedLock的實(shí)現(xiàn)原理,感興趣的可以了解下2024-02-02
利用Redis實(shí)現(xiàn)SQL伸縮的方法簡(jiǎn)介
這篇文章主要介紹了利用Redis實(shí)現(xiàn)SQL伸縮的方法,包括講到了鎖和時(shí)間序列等方面來(lái)提升傳統(tǒng)數(shù)據(jù)庫(kù)的性能,需要的朋友可以參考下2015-06-06
為了使Redis在重啟之后仍能保證數(shù)據(jù)不丟失，需要將數(shù)據(jù)從內(nèi)存中以某種形式同步到硬盤(pán)中，這一過(guò)程就是持久化，本文重點(diǎn)給大家介紹Redis RDB技術(shù)底層原理實(shí)現(xiàn)方法，一起看看吧2021-09-09
基于redis實(shí)現(xiàn)的點(diǎn)贊功能設(shè)計(jì)思路詳解
點(diǎn)贊是我們現(xiàn)在經(jīng)常見(jiàn)到的一個(gè)效果，如朋友圈、微博都有點(diǎn)贊的效果，下面這篇文章主要跟大家分享了基于redis實(shí)現(xiàn)的點(diǎn)贊功能設(shè)計(jì)思路的相關(guān)資料，文中介紹的非常詳細(xì)，對(duì)大家實(shí)現(xiàn)點(diǎn)贊功能具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來(lái)一起看看吧。2017-05-05
在實(shí)際項(xiàng)目中,我們可能需要根據(jù)一定的條件來(lái)刪除部分key,這時(shí)候就需要用到模糊刪除操作這,下面篇文章主要給大家介紹了關(guān)于Redis如何批量刪除指定模糊的key的相關(guān)資料,需要的朋友可以參考下2024-08-08
Redis SAVE命令不可用問(wèn)題的原因和解決方案
遇到 ERR unknown command 'SAVE' 錯(cuò)誤表明Redis 服務(wù)器配置中禁用了 SAVE 命令,這是一個(gè)安全特性,通常在生產(chǎn)環(huán)境中會(huì)被禁用,本文給大家詳細(xì)介紹了解決方案,需要的朋友可以參考下2025-07-07