Redis和Kafka都用到的SkipList是怎樣的

這期內容當中小編將會給大家帶來有關Redis和Kafka都用到的SkipList是怎樣的，文章內容豐富且以專業的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

跳表被廣泛地運用到了各種緩存地實現當中，它的主要優點，就是可以跟紅黑樹、AVL等平衡樹一樣，做到比較穩定地插入、查詢與刪除。理論插入查詢刪除的算法時間復雜度為O(logN)。

什么是跳表

鏈表，相信大家都不陌生，維護一個有序的鏈表是一件非常簡單的事情，我們都知道，在一個有序的鏈表里面，查詢跟插入的算法復雜度都是O(n)。

我們能不能進行優化呢，比如我們一次比較兩個呢？那樣不就可以把時間縮小一半？

同理，如果我們4個4個比，那不就更快了？

跳表就是這樣的一種數據結構，結點是跳過一部分的，從而加快了查詢的速度。跳表跟紅黑樹又有什么差別呢？既然兩者的算法復雜度差不多，為什么Redis要使用跳表而不使用紅黑樹呢？跳表相對于紅黑樹，主要有這幾個優點：    1.代碼相對簡單，手寫個跳表還有可能，手寫個紅黑樹試試？    2.如果我們要查詢一個區間里面的值，用平衡樹可能會麻煩。這里的麻煩指的是實現和理解上，平衡二叉樹查詢一段區間也是可以做到的。    3.刪除一段區間，這個如果是平衡二叉樹，就會相當困難，畢竟設計到樹的平衡問題，而跳表則沒有這種煩惱。好了，相信你對跳表已經有一些認識了，我們來簡單介紹平衡二叉樹的幾個基本操作。

查詢

假如我們要查詢11，那么我們從最上層出發，發現下一個是5，再下一個是13，已經大于11，所以進入下一層，下一層的一個是9，查找下一個，下一個又是13，再次進入下一層。最終找到11。

是不是非常的簡單？我們可以把查找的過程總結為一條二元表達式（下一個是否大于結果？下一個：下一層）。理解跳表的查詢過程非常重要，試試看查詢其他數字，只要你理解了查詢，后面兩種都非常簡單。

插入

插入的時候，首先要進行查詢，然后從最底層開始，插入被插入的元素。然后看看從下而上，是否需要逐層插入。可是到底要不要插入上一層呢？我們都知道，我們想每層的跳躍都非常高效，越是平衡就越好（第一層1級跳，第二層2級跳，第3層4級跳，第4層8級跳）。但是用算法實現起來，確實非常地復雜的，并且要嚴格地按照2地指數次冪，我們還要對原有地結構進行調整。所以跳表的思路是拋硬幣，聽天由命，產生一個隨機數，50%概率再向上擴展，否則就結束。這樣子，每一個元素能夠有X層的概率為0.5^(X-1)次方。反過來，第X層有多少個元素的數學期望大家也可以算一下。

刪除

同插入一樣，刪除也是先查找，查找到了之后，再從下往上逐個刪除。比較簡單，就不再贅敘。
  Kafka的運用Kafka 的每個日志對象中使用了 ConcurrentSkipListMap 來保存各個日志分段，每個日志分段的 baseOffset 作為 key，這樣可以根據指定偏移量來快速定位到消息所在的日志分段。

總結

跳表，用了計算機中一場非常用的解決問題的思路，隨機。隨機在深度學習與人工智能領域運用得非常的廣泛。

上述就是小編為大家分享的Redis和Kafka都用到的SkipList是怎樣的了，如果剛好有類似的疑惑，不妨參照上述分析進行理解。如果想知道更多相關知識，歡迎關注億速云行業資訊頻道。