二叉搜索樹

二叉搜索樹(Binary Search Tree募逞，簡(jiǎn)寫B(tài)ST)蛋铆，又稱為二叉排序樹，屬于樹的一種放接，通過二叉樹將數(shù)據(jù)組織起來刺啦，樹的每個(gè)節(jié)點(diǎn)都包含了健值 key、數(shù)據(jù)值 data纠脾、左子節(jié)點(diǎn)指針玛瘸、右子節(jié)點(diǎn)指針蜕青。其中健值 key 是最核心的部分，它的值決定了樹的組織形狀糊渊；數(shù)據(jù)值 data 是該節(jié)點(diǎn)對(duì)應(yīng)的數(shù)據(jù)右核，有些場(chǎng)景可以忽略，舉個(gè)例子渺绒，key 為身份證號(hào)而 data 為人名贺喝，通過身份證號(hào)找人名绎巨；左子節(jié)點(diǎn)指針指向左子節(jié)點(diǎn)瞻想；右子節(jié)點(diǎn)指針指向右子節(jié)點(diǎn)。

二叉搜索樹特點(diǎn)

• 左右子樹也分別是二叉搜索樹谋逻。
• 左子樹的所有節(jié)點(diǎn) key 值都小于它的根節(jié)點(diǎn)的 key 值殷绍。
• 右子樹的所有節(jié)點(diǎn) key 值都大于他的根節(jié)點(diǎn)的 key 值挠他。
• 二叉搜索樹可以為一棵空樹。
• 一般來說篡帕，樹中的每個(gè)節(jié)點(diǎn)的 key 值都不相等，但根據(jù)需要也可以將相同的 key 值插入樹中贸呢。

AVL樹

AVL樹镰烧，也稱平衡二叉搜索樹，AVL是其發(fā)明者姓名簡(jiǎn)寫楞陷。AVL樹屬于樹的一種怔鳖，而且它也是一棵二叉搜索樹，不同的是他通過一定機(jī)制能保證二叉搜索樹的平衡固蛾，平衡的二叉搜索樹的查詢效率更高结执。

AVL樹特點(diǎn)

• AVL樹是一棵二叉搜索樹。
• AVL樹的左右子節(jié)點(diǎn)也是AVL樹艾凯。
• AVL樹擁有二叉搜索樹的所有基本特點(diǎn)献幔。
• 每個(gè)節(jié)點(diǎn)的左右子節(jié)點(diǎn)的高度之差的絕對(duì)值最多為1，即平衡因子為范圍為[-1,1]趾诗。

紅黑樹

紅黑(Red-black)樹是一種自平衡二叉查找樹蜡感，1972年由Rudolf Bayer發(fā)明，它與AVL樹類似恃泪，都在插入和刪除操作時(shí)能通過旋轉(zhuǎn)操作保持二叉查找樹的平衡郑兴，以便能獲得高效的查找性能。

它可以在 O(logn) 時(shí)間內(nèi)做查找贝乎，插入和刪除等操作情连。紅黑樹是2-3-4樹的一種等同，但有些紅黑樹設(shè)定只能左邊是紅樹览效，這種情況就是2-3樹的一種等同了却舀。

對(duì)于AVL樹來說虫几，紅黑樹犧牲了部分平衡性以換取插入/刪除操作時(shí)少量的旋轉(zhuǎn)操作，整體來說性能要優(yōu)于AVL樹禁筏。

紅黑樹性質(zhì)

• 節(jié)點(diǎn)是紅色或黑色持钉。
• 根節(jié)點(diǎn)是黑色。
• 每個(gè)葉節(jié)點(diǎn)（NIL節(jié)點(diǎn)）是黑色的篱昔。
• 每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都為黑色每强。(從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn))
• 從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。

2-3樹

2-3樹州刽，是最簡(jiǎn)單的B-樹空执，其中2、3主要體現(xiàn)在每個(gè)非葉子節(jié)點(diǎn)都有2個(gè)或3個(gè)子節(jié)點(diǎn)穗椅，B-樹即是平衡樹辨绊，平衡樹是為了解決不平衡樹查詢效率問題，常見的二叉平衡書有AVL樹匹表，它雖然提高了查詢效率门坷，但是插入操作效率不高，因?yàn)樗枰倜看尾迦牍?jié)點(diǎn)后維護(hù)樹的平衡袍镀，而為了解決查詢效率同時(shí)有兼顧插入效率默蚌，于是提出了2-3樹。

2-3樹特點(diǎn)

• 2-3樹是一棵平衡樹苇羡，但不是二叉平衡樹绸吸。
• 對(duì)于高度相同的2-3樹和二叉樹，2-3樹的節(jié)點(diǎn)數(shù)要大于滿二叉樹设江，因?yàn)橛行┕?jié)點(diǎn)可能有三個(gè)子節(jié)點(diǎn)锦茁。
• 2-3樹可以是一棵空樹。
• 對(duì)于2節(jié)點(diǎn)來說叉存，該節(jié)點(diǎn)保存了一個(gè)key及對(duì)應(yīng)的value码俩，除此之外還保存了指向左右兩邊的子節(jié)點(diǎn)，子節(jié)點(diǎn)也是一個(gè)2-3節(jié)點(diǎn)歼捏，左子節(jié)點(diǎn)所有值小于key握玛，右子節(jié)點(diǎn)所有值大于key。
• 對(duì)于3節(jié)點(diǎn)來說甫菠，該節(jié)點(diǎn)保存了兩個(gè)key及對(duì)應(yīng)的value挠铲，除此之外還保存了指向左中右三個(gè)方向的子節(jié)點(diǎn)，子節(jié)點(diǎn)也是一個(gè)2-3節(jié)點(diǎn)寂诱，左子節(jié)點(diǎn)的所有值小于兩個(gè)key中較小的那個(gè)拂苹，中節(jié)點(diǎn)的所有值在兩個(gè)key值之間，右子節(jié)點(diǎn)大于兩個(gè)key中較大的那個(gè)。
• 對(duì)2-3樹進(jìn)行中序遍歷能得到一個(gè)排好序的序列瓢棒。

B樹

B樹即平衡查找樹浴韭，一般理解為平衡多路查找樹，也稱為B-樹脯宿、B_樹念颈。是一種自平衡樹狀數(shù)據(jù)結(jié)構(gòu)，能對(duì)存儲(chǔ)的數(shù)據(jù)進(jìn)行O(log n)的時(shí)間復(fù)雜度進(jìn)行查找连霉、插入和刪除榴芳。B樹一般較多用在存儲(chǔ)系統(tǒng)上，比如數(shù)據(jù)庫或文件系統(tǒng)跺撼。

B樹特點(diǎn)

• B樹可以定義一個(gè)m值作為預(yù)定范圍窟感，即m路(階)B樹。
• 每個(gè)節(jié)點(diǎn)最多有m個(gè)孩子歉井。
• 每個(gè)節(jié)點(diǎn)至少有ceil(m/2)個(gè)孩子柿祈，除了根節(jié)點(diǎn)和葉子節(jié)點(diǎn)外。
• 對(duì)于根節(jié)點(diǎn)哩至，子樹個(gè)數(shù)范圍為[2,m]躏嚎，節(jié)點(diǎn)內(nèi)值的個(gè)數(shù)范圍為[1,m-1]。
• 對(duì)于非根節(jié)點(diǎn)菩貌，節(jié)點(diǎn)內(nèi)的值個(gè)數(shù)范圍為[ceil(m/2)-1,m-1]紧索。
• 根節(jié)點(diǎn)(非葉子節(jié)點(diǎn))至少有兩個(gè)孩子。
• 一個(gè)有k個(gè)孩子的非葉子節(jié)點(diǎn)包含k-1個(gè)值菜谣。
• 所有葉子節(jié)點(diǎn)在同一層。
• 節(jié)點(diǎn)內(nèi)的值按照從小到大排列晚缩。
• 父節(jié)點(diǎn)的若干值作為分離值分成多個(gè)子樹尾膊，左子樹小于對(duì)應(yīng)分離值，對(duì)應(yīng)分離值小于右子樹荞彼。

B+樹

B+樹是B樹的一種變體冈敛，也屬于平衡多路查找樹，大體結(jié)構(gòu)與B樹相同鸣皂，包含根節(jié)點(diǎn)抓谴、內(nèi)部節(jié)點(diǎn)和葉子節(jié)點(diǎn)。多用于數(shù)據(jù)庫和操作系統(tǒng)的文件系統(tǒng)中寞缝，由于B+樹內(nèi)部節(jié)點(diǎn)不保存數(shù)據(jù)癌压，所以能在內(nèi)存中存放更多索引，增加緩存命中率荆陆。另外因?yàn)槿~子節(jié)點(diǎn)相連遍歷操作很方便滩届，而且數(shù)據(jù)也具有順序性，便于區(qū)間查找被啼。

B+樹特點(diǎn)

• B+樹可以定義一個(gè)m值作為預(yù)定范圍帜消，即m路(階)B+樹棠枉。
• 根節(jié)點(diǎn)可能是葉子節(jié)點(diǎn)，也可能是包含兩個(gè)或兩個(gè)以上子節(jié)點(diǎn)的節(jié)點(diǎn)泡挺。
• 內(nèi)部節(jié)點(diǎn)如果擁有k個(gè)關(guān)鍵字則有k+1個(gè)子節(jié)點(diǎn)辈讶。
• 非葉子節(jié)點(diǎn)不保存數(shù)據(jù)，只保存關(guān)鍵字用作索引娄猫，所有數(shù)據(jù)都保存在葉子節(jié)點(diǎn)中贱除。
• 非葉子節(jié)點(diǎn)有若干子樹指針，如果非葉子節(jié)點(diǎn)關(guān)鍵字為k1,k2,...kn稚新，其中n=m-1勘伺，那么第一個(gè)子樹關(guān)鍵字判斷條件為小于k1，第二個(gè)為大于等于k1而小于k2褂删，以此類推飞醉，最后一個(gè)為大于等于kn，總共可以劃分出m個(gè)區(qū)間屯阀，即可以有m個(gè)分支缅帘。（判斷條件其實(shí)沒有嚴(yán)格的要求，只要能實(shí)現(xiàn)對(duì)B+樹的數(shù)據(jù)進(jìn)行定位劃分即可难衰，有些實(shí)現(xiàn)使用了m個(gè)關(guān)鍵字來劃分區(qū)間钦无，也是可以的）
• 所有葉子節(jié)點(diǎn)通過指針鏈相連，且葉子節(jié)點(diǎn)本身按關(guān)鍵字的大小從小到大順序排列盖袭。
• 自然插入而不進(jìn)行刪除操作時(shí)失暂，葉子節(jié)點(diǎn)項(xiàng)的個(gè)數(shù)范圍為[floor(m/2),m-1]，內(nèi)部節(jié)點(diǎn)項(xiàng)的個(gè)數(shù)范圍為[ceil(m/2)-1,m-1]鳄虱。
• 另外通常B+樹有兩個(gè)頭指針弟塞，一個(gè)指向根節(jié)點(diǎn)一個(gè)指向關(guān)鍵字最小的葉子節(jié)點(diǎn)。
• 在進(jìn)行刪除操作時(shí)拙已，涉及到索引節(jié)點(diǎn)填充因子和葉子節(jié)點(diǎn)填充因子决记，一般可設(shè)葉子節(jié)點(diǎn)和索引節(jié)點(diǎn)的填充因子都不少于50%。

關(guān)于LSM樹

LSM樹倍踪，即日志結(jié)構(gòu)合并樹(Log-Structured Merge-Tree)系宫。其實(shí)它并不屬于一個(gè)具體的數(shù)據(jù)結(jié)構(gòu)，它更多是一種數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)思想建车。大多NoSQL數(shù)據(jù)庫核心思想都是基于LSM來做的扩借，只是具體的實(shí)現(xiàn)不同。

LSM樹誕生背景

傳統(tǒng)關(guān)系型數(shù)據(jù)庫使用btree或一些變體作為存儲(chǔ)結(jié)構(gòu)缤至，能高效進(jìn)行查找往枷。但保存在磁盤中時(shí)它也有一個(gè)明顯的缺陷，那就是邏輯上相離很近但物理卻可能相隔很遠(yuǎn)，這就可能造成大量的磁盤隨機(jī)讀寫错洁。隨機(jī)讀寫比順序讀寫慢很多秉宿，為了提升IO性能，我們需要一種能將隨機(jī)操作變?yōu)轫樞虿僮鞯臋C(jī)制屯碴，于是便有了LSM樹描睦。LSM樹能讓我們進(jìn)行順序?qū)懘疟P，從而大幅提升寫操作导而，作為代價(jià)的是犧牲了一些讀性能忱叭。

關(guān)于磁盤IO

磁盤讀寫時(shí)涉及到磁盤上數(shù)據(jù)查找，地址一般由柱面號(hào)今艺、盤面號(hào)和塊號(hào)三者構(gòu)成韵丑。也就是說移動(dòng)臂先根據(jù)柱面號(hào)移動(dòng)到指定柱面，然后根據(jù)盤面號(hào)確定盤面的磁道虚缎，最后根據(jù)塊號(hào)將指定的磁道段移動(dòng)到磁頭下撵彻，便可開始讀寫。
整個(gè)過程主要有三部分時(shí)間消耗实牡，查找時(shí)間(seek time) +等待時(shí)間(latency time)+傳輸時(shí)間(transmission time) 陌僵。分別表示定位柱面的耗時(shí)、將塊號(hào)指定磁道段移到磁頭的耗時(shí)创坞、將數(shù)據(jù)傳到內(nèi)存的耗時(shí)碗短。整個(gè)磁盤IO最耗時(shí)的地方在查找時(shí)間，所以減少查找時(shí)間能大幅提升性能题涨。

Radix樹

Radix樹偎谁，即基數(shù)樹，也稱壓縮前綴樹纲堵，是一種提供key-value存儲(chǔ)查找的數(shù)據(jù)結(jié)構(gòu)巡雨。與Trie不同的是，它對(duì)Trie樹進(jìn)行了空間優(yōu)化婉支，只有一個(gè)子節(jié)點(diǎn)的中間節(jié)點(diǎn)將被壓縮。同樣的澜建，Radix樹的插入向挖、查詢、刪除操作的時(shí)間復(fù)雜度都為O(k)炕舵。

Radix樹特點(diǎn)

一般由根節(jié)點(diǎn)何之、中間節(jié)點(diǎn)和葉子節(jié)點(diǎn)組成。
每個(gè)節(jié)點(diǎn)可以包含一個(gè)或多個(gè)字符咽筋。
樹的葉子結(jié)點(diǎn)數(shù)即是數(shù)據(jù)條目數(shù)溶推。
從根節(jié)點(diǎn)到某一節(jié)點(diǎn)經(jīng)過路徑的字符連起來即為該節(jié)點(diǎn)對(duì)應(yīng)的字符串。
每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)字符串都不相同