文件系統和資料庫是由於什麼原因才選擇 B 樹或 B+ 樹建立索引的？

01-11

這是配合磁碟特性的，本來查詢樹使用多分支在內存里是沒有意義的，只會導致讀取了更多數據，但磁碟（或者說機械硬碟）的特性在於，多次隨機讀取效率遠低於連續讀取一大段數據，因為每一次都需要經過尋道。這樣B樹就被設計為用較少的次數讀取磁碟，每次讀取較大的塊，從而優化整體查詢。

理解這個問題得理解幾個知識點：

1. 磁碟IO比內存操作性是相差千級數量級的差異，因此應該盡量減少io操作

2. 磁碟組織形式是扇區，因為數據的局部性，因此一次磁碟io會把一個扇區的都預讀出來，也就是說你一次讀1位元組的數據和4K位元組（一個扇區）需要的時間是幾乎一樣的。

理解了這幾個知識點之後再來看索引設計為什麼要用B+樹：

索引的目標是要找到數據所在的物理位置，因此用樹去實現搜索數據所在物理位置，每個節點對應一次IO，因此結合知識點1為了減少搜索時間，就需要控制樹的高度，那這樣的話二叉樹明顯不行，因為二叉樹插入的話樹的高度是沒辦法控制的，因此採用B+樹的形式，每個節點對應很多子節點，插入節點時增加子節點而不是增加樹高度。更進一步，採用B+樹時在相同數據量的情況下如何降低樹的高度？當然是增加每一層的數據量，而考慮到知識點2，一個節點對應一個扇區大小存儲多個數據項，既可以降低索引文件大小，又可以在相同數據量的情況下減少每層節點數，提高性能。

有一個數據可以作為參考，500W條數據用B+樹可以控制在三層以內。

減少磁碟 seek 次數。

從 MongoDB 及 Mysql 談B/B+樹

http://m.blog.csdn.net/wwh578867817/article/details/50493940

索引主要是為了加快查詢，不然得全表/盤掃描。B樹的特點是height小，葉子在同層（這樣cost基本一致），而且是按順序的，方便做範圍查找。

其他我能想到的數據結構，hash的話，不可避免的要解決衝突問題，數據量大的肯定不適合了，而且也沒有範圍查找，還浪費空間。

二叉、紅黑這些常用的樹，分叉太少，height大，就算node小也沒法用局部性原理加快（父子node物理上不在一塊），索引查找的時候磁碟seek消耗太大（索引一般在磁碟上）不如b樹一個node大點但是h小，幾次seek載入就完了

以前的筆記，有錯還請大家指正。謝謝！

在磁碟IO時間和樹查找時間的取捨中取得一個平衡。

樹結構可以將查詢時間複雜度降到對數級別，理論上二叉樹最快。然而完全用二叉樹的磁碟IO太多，如果可以把一段數據整個load進內存，再進行查找，不一定比把所有內容做成二叉樹，在磁碟查找慢。

減少磁頭尋道次數，和預讀

《編程之法：面試和演算法心得》這本書中有一節關於B樹講的比較清楚。

julycoding/The-Art-Of-Programming-By-July

其實主要原因就是減少讀寫磁碟的次數。其它答主都已經回答了，我這裡畫蛇添足（把為什麼三個字好好解釋一番），較為詳細的具體解釋一下，不對的地方，還請海涵並敬請賜教。

磁碟與主存的速度差： 讀取DRAM(主存)的速度是讀寫磁碟速度的大約10萬倍（有些答主說幾千倍是不嚴謹滴，可以參考CSAPP 虛擬存儲器那一章），並且第一次讀寫某扇區第一位元組的速度比連續讀該磁碟其他位元組的速度慢約10萬倍。 了解了這麼大的速度差異後，聰明機智的你很自然的就想到，我每次讀寫磁碟時都儘可能多的讀數據，改寫了之後不直接回寫，必要的時候再寫回（也就是寫回式），應該能很大減少讀寫磁碟的次數。很顯然這就是B樹所做的事兒。
B樹的特點：首先B樹是很嚴格的平衡二叉搜索樹（葉子節點深度都相同，相比較而言紅黑樹那傢伙可沒這麼守規矩），每個節點中的關鍵字可以有很多。由於 1 中所述的原因， B樹的節點大小與磁碟頁一樣大（Linux中一般是4K）。至於為什麼要和磁碟也一樣大？這是和虛擬存儲器系統運行的機制有關，存儲器映射是虛擬頁（磁碟， linux中一般是4K）映射到物理頁（主存，Linux中一般是4K），然後由虛擬存儲器系統在背後默默地悄無聲息地完成數據移動的工作。這樣B樹的每個節點的關鍵字數就很多了，具體取決於關鍵字（及其所帶的衛星數據）相對於磁碟頁的大小，《演算法導論》（B樹章節）中說一般是50~2000之間。 這麼大的分支因子，使得B樹樹深較小，讀寫磁碟次數大大減少。由於B樹根節點一般常駐內存，很明顯，要讀取某一結點上的數據所需讀寫磁碟的次數就等於該節點的深度。並且由於讀寫數據一般都具有局部性（空間局部性和時間局部性）的原因，使得讀寫磁碟減少的次數比想像中的還好（你明明只是餓了，叫了份外賣，結果送外賣的還是個美女）。
B樹的插入和刪除： B樹插入和刪除的時候，是採用沿途分裂和沿途和並的方式進行的（真的好機智吖），基本上避免了回溯（刪除時有一種情況要回溯），也就是和查找時，讀寫磁碟的次數差不多。
為什麼是B+（B-）樹: 用B+樹的原因其實還是想讓一個節點中包含更多的關鍵字，B+樹把數據域都放到葉子節點上，這樣內部節點只剩關鍵字了，這樣一個節點（一個磁碟頁）就能包含更多的關鍵字了，降低樹深，減少讀寫磁碟次數！
MySQL中的B+樹： 據我所知，MySQL中MYISAM引擎，InnoDB引擎（其他引擎沒了解過，慚愧~~）都是以B+樹作為數據結構的，並且在B+樹葉子節點層添加了順序訪問的指針，從而加快順序訪問的速度。

綜上所述，選用B+樹（另外B樹就是B-樹，因為B樹英文是 B-Tree由於翻譯差異導致出現了 B樹和B-樹）。歡迎指正，敬請賜教！

首先應該關注為啥用樹，然後在關注為啥是b+樹。

磁碟文件是塊狀的，能夠對塊狀數據進行管理的數據結構有哪些，鏈表，map，樹;

map可以提供o1的時間複雜度，但是在資料庫區間查詢，幾乎沒辦法，捨棄;

鏈表可以提供鏈式的類區間查詢，但是時間複雜度on，隨著數據塊增多，查詢效率越來越差。

最後就還有樹，剛好在時間和功能取了兩者的優勢，塊的索引是對數級別，通過把葉子節點用鏈錶鏈接提供區間功能，所以選擇樹。

之所以為啥會是b+樹，其實前面回答已經解釋了。

當你從存儲媒介的特點，去尋找合適的數據結構，在對數據結構訂製，其實大概就這個思路。

手機碼子，辛苦，如有偏差，請斧正

可以說B樹, B+樹或者其它變種, 這種數據結構當初在設計的時候就差不多是為文件系統組織數據而設計的. 當然不能說一定要用B樹, 但是隨著伺服器需要的存儲越來越大, B樹的組織會更好的發揮作用.

B樹(就是B-樹)的層數少，檢索，插入數據和節點分裂時涉及的磁碟操作次數少。

B+樹的結構近似於B樹加入葉子節點鏈，這個特性主要是為了提高範圍檢索的性能。

https://www.youtube.com/watch?v=9Rb85cOXTKUlist=PLD2AE32F507F10481index=20

B+樹分支多高度低，一般最多三層，這樣查詢速度快。索引存在磁碟上，這樣一來，由於高度低，查詢次數就少很多

考慮到時間複雜度啦

文件系統對目錄的檢索，還有sqlite資料庫對錶單內容的檢索都是b樹。。都是為了快。。。。不然線性搜索就太慢了。ext2文件系統以前對目錄項的檢索匹配就是線性查找方式。這個真的太浪費時間了，隨著文件數量的增加，這個問題更明顯。後來就改進了。。

題主跑一下就知道begeekmyfriend/bplustree

理解二叉查找樹與B-/B+樹的區別，你就知道為什麼選擇B-/B+樹了！