redis使用跳躍表而不是樹的原因解析
Redis中支持五種數(shù)據(jù)類型中有序集合Sorted Set的底層數(shù)據(jù)結(jié)構(gòu)使用的跳躍表，為何不使用其他的如平衡二叉樹、b+樹等數(shù)據(jù)結(jié)構(gòu)呢？
1，redis的設(shè)計目標(biāo)、性能需求：
redis是高性能的非關(guān)系型（NoSQL）內(nèi)存鍵值數(shù)據(jù)庫，它以其快速的操作速度而聞名。
讀取速度：Redis能實現(xiàn)極高的讀取速度，據(jù)官方測試報告，可以達(dá)到每秒約110,000次讀取操作。
寫入速度：與讀取相比，寫入速度略低，但仍然相當(dāng)可觀，官方數(shù)據(jù)顯示，Redis的寫入速度大約是每秒81,000次操作。
類似產(chǎn)品如Memcached等，無法達(dá)到如此性能。
2，有序集合都可以借助什么數(shù)據(jù)結(jié)構(gòu)及其基本原理
有序集合需求：自然有序，查找高速，支持范圍查找
2.1，傳統(tǒng)數(shù)組/鏈表+排序
數(shù)組或鏈表可以存儲數(shù)據(jù)，可以新增或修改數(shù)據(jù)后重新排序，
而在集合排序方面，最快的歸并排序也需要O(NlongN)的時間復(fù)雜度。
時間不夠快，但實現(xiàn)、使用方面簡單
2.2，跳躍表（鏈表的優(yōu)化–鏈表+多級索引）
跳躍表最早是由William Pugh在1990年提出的，被用來代替平衡樹（如AVL樹和紅黑樹）來實現(xiàn)有序集合。跳躍表的查詢復(fù)雜度為O(log n)，與平衡樹相當(dāng)，但由于其實現(xiàn)較為簡單，所以在實際使用中比平衡樹更加高效。
例：查找90
增加指針，讓指針指向遠(yuǎn)處個節(jié)點，
如上圖，共四層，最底層（原鏈表L1）節(jié)點是10 - 20 - 30 -… - 120，中間層L2增加節(jié)點10 - 30 - 40 - 60 - 80 - 100 - 120，L2上層L3增加節(jié)點10 - 40 - 80 - 120 最高層10 - 120
這樣形成三個新的鏈表，但它包含的節(jié)點個數(shù)只有原來的一部分；
當(dāng)我們查找數(shù)據(jù)之時，先沿著這個最高層鏈表進(jìn)行查找。當(dāng)碰到比待查數(shù)據(jù)大的節(jié)點時，再到中間層，最后回到原來的鏈表中進(jìn)行查找。
如查找90，共經(jīng)歷6步。
過程類似二分查找，時間復(fù)雜度支持平均O(logN)，最壞O(N)的節(jié)點查找，還可以順序性操作來批量處理節(jié)點。
2.3，平衡二叉樹/紅黑樹
平衡二叉樹的查詢復(fù)雜度為O(logN)，但新增、刪除需要調(diào)整保持平衡，實現(xiàn)相對復(fù)雜；
范圍查詢方面，平衡二叉樹支持范圍查詢,但是這這種數(shù)據(jù)結(jié)構(gòu)要范圍查找要往回找,即回溯到父結(jié)點,而B+樹的葉子結(jié)點的指針的效率則更高
2.4，B+樹
B+ Tree是一種經(jīng)典的多路平衡查找樹，它通常被用來實現(xiàn)磁盤上的數(shù)據(jù)結(jié)構(gòu)。在B+ Tree中，每個節(jié)點可以包含多個鍵值對，而且所有葉子節(jié)點都被連接成一個鏈表。B+ Tree的查詢復(fù)雜度也是O(log n)，但由于其實現(xiàn)較為復(fù)雜，所以在實際使用中通常用于數(shù)據(jù)庫系統(tǒng)等需要高效讀寫的場景中。
3，跳躍表與平衡樹的實現(xiàn)
//redis源碼中跳躍表結(jié)構(gòu)的實現(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;如圖，一個跳表節(jié)點，有l(wèi)evel數(shù)組，每個元素都有一個指向其他節(jié)點的指針，可以通過這些層來加快訪問速度
3.1使用java實現(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é)點
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é)點
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é)點
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é)點
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實現(xiàn)平衡二叉樹（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é)點的高度
private int height(Node node) {
return (node == null) ? 0 : node.height;
}
// 獲取樹的平衡因子
private int getBalance(Node node) {
return (node == null) ? 0 : height(node.left) - height(node.right);
}
// 更新節(jié)點的高度
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é)點
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é)點的高度
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é)點
return node;
}
// 插入節(jié)點的公共接口
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é)點
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實現(xiàn)B+樹：
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+樹節(jié)點抽象類
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+樹葉子節(jié)點類
static class BPlusLeafNode extends BPlusNode {
List<String> values;
BPlusLeafNode next; // 用于連接葉子節(jié)點形成鏈表
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é)點
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é)點鏈表
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+樹內(nèi)部節(jié)點類
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é)點移至新節(jié)點
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)存占用、對范圍查找的支持、實現(xiàn)難易程度這三方面總結(jié)的原因，
簡單翻譯一下：
1、它們不是非常內(nèi)存密集型的?；旧嫌赡銢Q定。改變關(guān)于節(jié)點具有給定級別數(shù)的概率的參數(shù)將使其比 btree 占用更少的內(nèi)存。
2、Zset 經(jīng)常需要執(zhí)行 ZRANGE 或 ZREVRANGE 的命令，即作為鏈表遍歷跳表。通過此操作，跳表的緩存局部性至少與其他類型的平衡樹一樣好。
3、它們更易于實現(xiàn)、調(diào)試等。例如，由于跳表的簡單性，我收到了一個補(bǔ)?。ㄒ呀?jīng)在Redis master中），其中擴(kuò)展了跳表，在 O(log(N) 中實現(xiàn)了 ZRANK。它只需要對代碼進(jìn)行少量修改。
跳躍表的優(yōu)勢：
1，時間復(fù)雜度方面：大部分情況下，跳躍表的效率和平衡樹媲美；
2，算法實現(xiàn)方面：跳躍表的實現(xiàn)比平衡樹、b+樹更為簡單；
3，范圍查找方面，跳表比平衡樹操作要簡單，平衡樹需要回溯到父結(jié)點，條表可以做到 O(logn) 的時間復(fù)雜度定位區(qū)間的起點，然后在原始鏈表中順序往后遍歷；
4，對于小數(shù)據(jù)集的性能： 在某些場景下，跳表在小數(shù)據(jù)集上的性能可能優(yōu)于B+樹。跳表的查詢操作在某些情況下可能更迅速。
到此這篇關(guān)于redis使用跳躍表而不是樹的原因解析的文章就介紹到這了,更多相關(guān)redis為什么使用跳躍表而不是樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了Redis模仿手機(jī)驗證碼發(fā)送功能，通過示例代碼給大家講解通過用戶輸入手機(jī)號以及驗證碼進(jìn)行校驗，代碼簡單易懂，需要的朋友可以參考下2021-09-09
這篇文章主要介紹了redis操作,記錄總結(jié)了Redis客戶端、服務(wù)器、string、hash、list、發(fā)布/訂閱、事務(wù)等相關(guān)概念、原理與操作技巧,需要的朋友可以參考下2020-04-04
這篇文章主要介紹了Redis的性能,作者通過Visual Studio上的C#程序?qū)ζ溥M(jìn)行了分析,需要的朋友可以參考下2015-06-06
使用Redis獲取數(shù)據(jù)轉(zhuǎn)json,解決動態(tài)泛型傳參的問題
這篇文章主要介紹了使用Redis獲取數(shù)據(jù)轉(zhuǎn)json,解決動態(tài)泛型傳參的問題，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-07-07
redis的list數(shù)據(jù)類型相關(guān)命令介紹及使用
本文主要介紹了redis的list數(shù)據(jù)類型相關(guān)命令介紹及使用，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-01-01
這篇文章主要介紹了Linux下redis5.0.5的安裝過程與配置方法,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-11-11
這篇文章主要介紹了redis 限制內(nèi)存使用大小的實現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-05-05
這篇文章主要為大家介紹了redistemplate下opsForHash操作示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-07-07
今天小編就為大家分享一篇關(guān)于爬蟲技術(shù)之分布式爬蟲架構(gòu)的講解，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-01-01
本文主要介紹了Redis實現(xiàn)短信登錄的示例代碼，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-07-07