建站
咨詢
售后
建站咨詢
新聞中心
這期內(nèi)容當(dāng)中小編將會(huì)給大家?guī)碛嘘P(guān)redis和Kafka都用到的SkipList是怎樣的，文章內(nèi)容豐富且以專業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。
成都創(chuàng)新互聯(lián)專業(yè)為企業(yè)提供浚縣網(wǎng)站建設(shè)、浚縣做網(wǎng)站、浚縣網(wǎng)站設(shè)計(jì)、浚縣網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計(jì)與制作、浚縣企業(yè)網(wǎng)站模板建站服務(wù)，十載浚縣做網(wǎng)站經(jīng)驗(yàn)，不只是建網(wǎng)站，更提供有價(jià)值的思路和整體網(wǎng)絡(luò)服務(wù)。
跳表被廣泛地運(yùn)用到了各種緩存地實(shí)現(xiàn)當(dāng)中，它的主要優(yōu)點(diǎn)，就是可以跟紅黑樹、AVL等平衡樹一樣，做到比較穩(wěn)定地插入、查詢與刪除。理論插入查詢刪除的算法時(shí)間復(fù)雜度為O(logN)。
什么是跳表
鏈表，相信大家都不陌生，維護(hù)一個(gè)有序的鏈表是一件非常簡單的事情，我們都知道，在一個(gè)有序的鏈表里面，查詢跟插入的算法復(fù)雜度都是O(n)。
我們能不能進(jìn)行優(yōu)化呢，比如我們一次比較兩個(gè)呢？那樣不就可以把時(shí)間縮小一半？
同理，如果我們4個(gè)4個(gè)比，那不就更快了？
跳表就是這樣的一種數(shù)據(jù)結(jié)構(gòu)，結(jié)點(diǎn)是跳過一部分的，從而加快了查詢的速度。跳表跟紅黑樹又有什么差別呢？既然兩者的算法復(fù)雜度差不多，為什么Redis要使用跳表而不使用紅黑樹呢？跳表相對于紅黑樹，主要有這幾個(gè)優(yōu)點(diǎn)： 1.代碼相對簡單，手寫個(gè)跳表還有可能，手寫個(gè)紅黑樹試試？ 2.如果我們要查詢一個(gè)區(qū)間里面的值，用平衡樹可能會(huì)麻煩。這里的麻煩指的是實(shí)現(xiàn)和理解上，平衡二叉樹查詢一段區(qū)間也是可以做到的。 3.刪除一段區(qū)間，這個(gè)如果是平衡二叉樹，就會(huì)相當(dāng)困難，畢竟設(shè)計(jì)到樹的平衡問題，而跳表則沒有這種煩惱。好了，相信你對跳表已經(jīng)有一些認(rèn)識(shí)了，我們來簡單介紹平衡二叉樹的幾個(gè)基本操作。
查詢
假如我們要查詢11，那么我們從最上層出發(fā)，發(fā)現(xiàn)下一個(gè)是5，再下一個(gè)是13，已經(jīng)大于11，所以進(jìn)入下一層，下一層的一個(gè)是9，查找下一個(gè)，下一個(gè)又是13，再次進(jìn)入下一層。最終找到11。
是不是非常的簡單？我們可以把查找的過程總結(jié)為一條二元表達(dá)式（下一個(gè)是否大于結(jié)果？下一個(gè)：下一層）。理解跳表的查詢過程非常重要，試試看查詢其他數(shù)字，只要你理解了查詢，后面兩種都非常簡單。
插入
插入的時(shí)候，首先要進(jìn)行查詢，然后從最底層開始，插入被插入的元素。然后看看從下而上，是否需要逐層插入。可是到底要不要插入上一層呢？我們都知道，我們想每層的跳躍都非常高效，越是平衡就越好（第一層1級(jí)跳，第二層2級(jí)跳，第3層4級(jí)跳，第4層8級(jí)跳）。但是用算法實(shí)現(xiàn)起來，確實(shí)非常地復(fù)雜的，并且要嚴(yán)格地按照2地指數(shù)次冪，我們還要對原有地結(jié)構(gòu)進(jìn)行調(diào)整。所以跳表的思路是拋硬幣，聽天由命，產(chǎn)生一個(gè)隨機(jī)數(shù)，50%概率再向上擴(kuò)展，否則就結(jié)束。這樣子，每一個(gè)元素能夠有X層的概率為0.5^(X-1)次方。反過來，第X層有多少個(gè)元素的數(shù)學(xué)期望大家也可以算一下。
刪除
同插入一樣，刪除也是先查找，查找到了之后，再從下往上逐個(gè)刪除。比較簡單，就不再贅敘。
Kafka的運(yùn)用Kafka 的每個(gè)日志對象中使用了 ConcurrentSkipListMap 來保存各個(gè)日志分段，每個(gè)日志分段的 baseOffset 作為 key，這樣可以根據(jù)指定偏移量來快速定位到消息所在的日志分段。
總結(jié)
跳表，用了計(jì)算機(jī)中一場非常用的解決問題的思路，隨機(jī)。隨機(jī)在深度學(xué)習(xí)與人工智能領(lǐng)域運(yùn)用得非常的廣泛。
上述就是小編為大家分享的Redis和Kafka都用到的SkipList是怎樣的了，如果剛好有類似的疑惑，不妨參照上述分析進(jìn)行理解。如果想知道更多相關(guān)知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。
分享文章：Redis和Kafka都用到的SkipList是怎樣的
網(wǎng)頁鏈接：http://www.ef60e0e.cn/article/poigdi.html
