在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的時候异逐，往往學(xué)習(xí)的思路是直奔主題，學(xué)習(xí)各種大神們設(shè)計出來的結(jié)構(gòu)精妙的數(shù)據(jù)結(jié)構(gòu)插掂。但是灰瞻，這樣的學(xué)習(xí)方式使各個結(jié)構(gòu)在腦中形成了一個個孤島，沒有什么聯(lián)系辅甥。
如果換個角度酝润，從問題入手，看看為了解決特定的問題璃弄，我們需要什么樣的數(shù)據(jù)結(jié)構(gòu)來更好地解決問題要销，在一步步解決問題的過程中，看看結(jié)構(gòu)之間的聯(lián)系是怎么樣的夏块，這樣的學(xué)習(xí)效果會不會好一些疏咐？
現(xiàn)在就來試一試，從解決查找問題為切入點拨扶，延伸到B樹凳鬓，B+樹。
問題是什么患民？
從計算機(jī)誕生以來缩举，數(shù)據(jù)就未曾離開過計算機(jī)。人類與計算機(jī)交互所產(chǎn)生的輸入匹颤、操作系統(tǒng)仅孩、運行在操作系統(tǒng)上的軟件、軟件處理的業(yè)務(wù)信息印蓖，這些都是數(shù)據(jù)辽慕，而計算機(jī)的運行過程就是對各種數(shù)據(jù)做計算的過程。這時問題就來了赦肃，計算機(jī)要處理的數(shù)據(jù)從何而來溅蛉？
如何看待存儲設(shè)備
數(shù)據(jù)存儲在存儲設(shè)備中公浪，比如內(nèi)存、硬盤船侧。
先看看內(nèi)存欠气。
內(nèi)存從結(jié)構(gòu)上來看，像是一個由點組成的矩陣镜撩，行的長度是8预柒，寬度則視內(nèi)存大小而定，每個點是一個bit袁梗，存儲著0宜鸯、1值。一行由8個點組成遮怜，即一行是8bit淋袖，即1byte。
CPU訪問內(nèi)存的方式是通過內(nèi)存地址锯梁，每個內(nèi)存地址指向的bit都是位于矩陣的第一列的bit适贸，并且一次對內(nèi)存的訪問會獲取8bit(1byte)或16bit(2byte)或32bit(byte)等等，即獲取8n bit(n byte)涝桅，n值由CPU位數(shù)決定。
根據(jù)CPU對于內(nèi)存的訪問方式烙样，可以把上邊所說的由點組成的矩陣冯遂，抽象成由 地址-數(shù)據(jù) 兩列組成的表，通過一個內(nèi)存地址谒获，就能獲取到相對應(yīng)的數(shù)據(jù)蛤肌。
再看看磁盤。
磁盤中的數(shù)據(jù)存儲在多張盤片上批狱，每張盤片以圓心為軸裸准，劃分為多個磁道，每個磁道上等距離的分布著多個點赔硫，點中記錄著0炒俱、1信號。因此要訪問磁盤中的某個bit數(shù)據(jù)爪膊，需要指定在哪張盤片权悟、哪個磁道、哪個位置推盛。能不能通過抽象來簡化對磁盤的訪問峦阁？這樣嘗試一下，把每個盤片以圓心為軸分割成多個扇面耘成，每個扇面512Byte榔昔，再把每個盤片的每個扇面按順序編上序號驹闰，這樣訪問磁盤的方式就變成了通過一個扇面編號，就能獲取到相對應(yīng)的512byte數(shù)據(jù)撒会，即抽象成了由 扇面標(biāo)號-數(shù)據(jù) 兩列組成的表嘹朗。
無論是內(nèi)存，還是磁盤茧彤，對數(shù)據(jù)的訪問都可以抽象成一張表骡显，表的第一列是我們?nèi)〉脭?shù)據(jù)需要的憑證，第二列是對應(yīng)的數(shù)據(jù)曾掂。
我們可以認(rèn)為惫谤，這就是數(shù)據(jù)結(jié)構(gòu)中所說的線性結(jié)構(gòu)，屬于最基本珠洗、最原始的結(jié)構(gòu)溜歪。所以無論是訪問內(nèi)存、還是訪問磁盤许蓖，我們都認(rèn)為是對線性結(jié)構(gòu)的訪問蝴猪。
下邊把內(nèi)存、磁盤中的數(shù)據(jù)統(tǒng)稱為線性結(jié)構(gòu)膊爪。
如何從線性結(jié)構(gòu)找到想要的數(shù)據(jù)
完成了上邊的抽象自阱，我們開始考慮一個問題：假設(shè)在線性結(jié)構(gòu)中存儲著數(shù)據(jù)A，我們想通過數(shù)據(jù)A的標(biāo)識來找到它米酬，該怎么做沛豌？
1. 順序遍歷
最簡單的方式，就是對線性結(jié)構(gòu)從頭到尾的找赃额，看看哪個數(shù)據(jù)是我們要的數(shù)據(jù)加派。
這個方式簡單可行，很容易就達(dá)到了目的跳芳。
這時出現(xiàn)了一個新的問題芍锦，如果線性結(jié)構(gòu)的長度越來越長，用上邊的方式會怎樣飞盆？
如果目標(biāo)數(shù)據(jù)位于第1000項娄琉，我們需要比較1000次標(biāo)識才能找到，也就是說有999次無意義的比較桨啃，尤其是在線性結(jié)構(gòu)長且目標(biāo)數(shù)據(jù)位于偏后的位置時车胡。
既然這樣，那可不可以避免無意義的比較來提高查找的效率照瘾？
2. 哈希表
現(xiàn)在嘗試著在線性結(jié)構(gòu)之外構(gòu)造一個新的結(jié)構(gòu)--哈希表匈棘，這個結(jié)構(gòu)能夠根據(jù)要查找的數(shù)據(jù)，直接定位到數(shù)據(jù)的位置析命，從而提高查找效率主卫。
這次逃默，不管數(shù)據(jù)有多少，我們能夠用1次計算就能找到數(shù)據(jù)A了簇搅，在效率上不能更快了完域！
這里對哈希表做了簡化，實際上會有哈希沖突的問題瘩将，這個問題會影響查找的效率吟税，影響程度取決于哈希表的寬度和哈希算法的離散程度，這里不展開討論姿现。
不過還是存在著問題框杜。哈希表與線性結(jié)構(gòu)是一一映射的關(guān)系孟辑，這就代表了哈希表的大小會隨著線性結(jié)構(gòu)的增大而增大，這在線性結(jié)構(gòu)很大的情況下是一筆不小的空間開銷。也就是說弱贼，哈希表是一種用空間換時間的策略喘落。
那么荒叼，下一個問題來了：在不犧牲空間的前提下方妖，能不能得到一個較高的查找效率？
3. 二叉查找樹
想要不犧牲過多的空間拌屏，同時還要得到比順序遍歷更高的查找效率潮针，這就代表著我們得讓線性結(jié)構(gòu)本身具備某種線索能夠引導(dǎo)我們找到目標(biāo)的數(shù)據(jù)。所以我們把線性結(jié)構(gòu)構(gòu)造成樹結(jié)構(gòu)：
構(gòu)建后的結(jié)構(gòu)不夠直觀倚喂，用樹形表示看下：
可以看到然低，在構(gòu)建后的二叉搜索樹中查找數(shù)據(jù)A的過程進(jìn)行了3次比較，而用順序查找的方式是3次比較务唐，效率確實提高了些，但是看上去提高的不明顯带兜。我們對順序查找和二叉搜索樹查找的效率進(jìn)行量化看看枫笛。
假設(shè)數(shù)據(jù)量為n。
對于順序查找刚照，最好的比較次數(shù)是1刑巧，即第一個就是目標(biāo)數(shù)據(jù)；最壞的比較次數(shù)是n无畔，即最后一個是目標(biāo)數(shù)據(jù)啊楚。那么平均查找次數(shù) = (n+1)/2 ≈ O(n)
對于二叉搜索樹，最好的比較次數(shù)是1浑彰，即根節(jié)點是目標(biāo)數(shù)據(jù)恭理；最壞的比較次數(shù)是log(n+1)，即根節(jié)點是葉子節(jié)點郭变。那么平均查找次數(shù) = (log(n+1) + 1)/2 ≈ O(logn)
其實二叉搜索樹的最壞比較次數(shù)是n颜价，也就是當(dāng)樹被構(gòu)建成只有左子樹或者右子樹的時候涯保，這里就不講樹的平衡了，把注意力都放在主要的思路上周伦。所以夕春，我默認(rèn)構(gòu)建出來的樹都是平衡二叉樹，下文也是一樣专挪。
看看兩種查找的時間復(fù)雜度曲線及志，由此看出，當(dāng)數(shù)據(jù)量大的時候寨腔，二叉搜索樹的平均查找效率高于順序查找速侈，因此此結(jié)構(gòu)可以滿足不犧牲空間同時還能提高查找效率的需求。
我們?nèi)匀荒茉谶@個方案上發(fā)現(xiàn)問題脆侮。假設(shè)線性結(jié)構(gòu)的數(shù)量極大锌畸，內(nèi)存空間已無法容納，那么我們就不得不在磁盤中來存儲這份數(shù)據(jù)靖避。這時問題來了潭枣，如果要在存儲在磁盤中的二叉搜索樹里查找數(shù)據(jù)，需要平均訪問logn次磁盤（由上文的時間復(fù)雜度得出）幻捏，比如n=100k盆犁，則一次查找要平均訪問磁盤17次，這個很要命篡九，要知道讀取機(jī)械硬盤的時間是幾十毫秒的級別谐岁，即使是SSD也得是幾十微秒，這和讀取內(nèi)存的納秒級別的速度差距非常大榛臼。因此伊佃，在這種情況下，硬盤的讀取速度導(dǎo)致了二叉搜索樹的查找速度非常緩慢沛善。
既然硬盤的讀取速度是效率的瓶頸航揉，那么能不能找到某種方式，通過減少讀取硬盤的次數(shù)來提高效率金刁？
B樹
在二叉搜索樹中查找數(shù)據(jù)帅涂，每向下遍歷一層，則需要多訪問一次磁盤尤蛮。那么媳友，可以通過減少樹的深度來減少讀取磁盤的次數(shù)。
我們在二叉搜索樹的基礎(chǔ)上产捞，拓展一下每個節(jié)點醇锚，即讓每個節(jié)點從只能存儲一份數(shù)據(jù)，拓展到最多存儲兩份數(shù)據(jù)坯临。這樣每個節(jié)點能夠存儲1份或2份數(shù)據(jù)搂抒，所以每個節(jié)點長度不一定相等艇搀，需要通過指針來指向下一個節(jié)點，這個就是B樹求晶。
可以看出來焰雕，拓展之后的樹的深度比原來少了1，所以最壞的情況下比較次數(shù)比原來少了1次芳杏，達(dá)到了減少訪問磁盤次數(shù)的目的矩屁。
那我們猜想一下，如果再擴(kuò)展每個節(jié)點的數(shù)據(jù)爵赵，拓展成3份吝秕、4份....m份，那么節(jié)點會越來越寬空幻，樹的深度會越來越小烁峭。
假設(shè)我們構(gòu)建了一棵每個節(jié)點存儲8份數(shù)據(jù)、深度為3的B樹秕铛，那么深度為1的節(jié)點有1個约郁，總共存儲了1*8=8份數(shù)據(jù)；深度為2的節(jié)點有1*(8+1)=9個但两，總共存儲了9*8=72份數(shù)據(jù)鬓梅；深度為3的節(jié)點有9*(8+1)=81個，總共存儲了81*8=680份數(shù)據(jù)谨湘。綜上绽快，總共可存儲8+72+680=760份數(shù)據(jù)。也就是說我們對這760份數(shù)據(jù)做查找最多訪問磁盤3次紧阔，和上邊說的存儲了7份數(shù)據(jù)的搜索二叉樹持平坊罢。
為了達(dá)到效率最優(yōu)，B樹的節(jié)點大小往往被設(shè)置成與磁盤扇區(qū)大小一致擅耽，一般為512艘绍。因為一般讀取磁盤的單位是扇區(qū)，這樣的設(shè)置充分利用了每次對磁盤的讀取秫筏，從而減少讀取次數(shù)。
B樹解決了磁盤讀取過多導(dǎo)致查找效率低的問題挎挖，但它存在著查找之外的其他問題：如果我們想按順序遍歷一遍所有數(shù)據(jù)这敬，需要怎么做？以上面的圖為例蕉朵，遍歷A->B->C->D->E->F崔涂，這個過程中訪問了兩次B和F所在節(jié)點。也就是說非葉子節(jié)點需要訪問多次始衅，這樣并不理想冷蚂。
那么缭保，有什么辦法能在滿足B樹特性的前提下還可以高效的順序遍歷所有數(shù)據(jù)？
B+樹
把B樹節(jié)點中的數(shù)據(jù)都放到葉子節(jié)點中蝙茶，而非葉子節(jié)點中只保留標(biāo)識和指針艺骂，看看結(jié)構(gòu)是什么樣的：
它依然保留著B樹的特性，同時還有些不同隆夯。B+樹只有遍歷到了葉子節(jié)點才能獲取到數(shù)據(jù)钳恕，非葉子節(jié)點中只有標(biāo)識信息，這導(dǎo)致查找的效率變低了蹄衷，但這換來的是所有數(shù)據(jù)都集中在了葉子節(jié)點中忧额，從而能夠按順序串聯(lián)在一起，實現(xiàn)高效的遍歷愧口。
總結(jié)
本文從對存儲設(shè)備中的數(shù)據(jù)做查找的問題開始討論睦番，一步步找到解決方案，同時發(fā)現(xiàn)新的問題耍属，如此往復(fù)直到延伸到B+樹托嚣。這里沒有討論具體的細(xì)節(jié)，比如如何解決哈希沖突恬涧、如何構(gòu)建平衡二叉樹等等注益，我希望把注意力放在在發(fā)現(xiàn)問題和解決問題的過程中，在這個過程中逐漸衍生出新的結(jié)構(gòu)溯捆，并用這些結(jié)構(gòu)來解決特定的問題丑搔，從而對這些結(jié)構(gòu)能有個新的認(rèn)識。
這里只涉及了小部分的數(shù)據(jù)結(jié)構(gòu)和查找這一個問題域提揍，其他的結(jié)構(gòu)和問題還有很多啤月，我相信也可以通過這種形式來思考一下，也許也會有同樣新的認(rèn)識劳跃。
如果本次的討論有那些不嚴(yán)謹(jǐn)?shù)牡胤交阎伲Ｍl(fā)現(xiàn)的人能幫我糾正一下，算是對我的幫助吧刨仑。
歡迎交流~
