### B-樹 我們知道B-樹每個節點上包含著數據和指針，每個指針指向其一個子節點的位置， B-樹的查找需要一次對每個節點進行二分查找，直至找到或返回null。通常，可以引入布朗過濾器等方式加速查找。B-樹的搜索，從根結點開始，對結點內的關鍵字（有序）序列進行二分查找，如果命中則結束，否則進入查詢關鍵字所屬范圍的兒子結點；重復，直到所對應的兒子指針為空，或已經是葉子結點(其搜索性能等價于在關鍵字全集內做一次二分查找)。 應用場景： - 一般B-樹常常作為磁盤的查找的數據結構使用。 - 一般磁盤為了減少尋道時間，往往會進行預讀，一次讀入1個或多個page的數據。我們只要將B-樹的每個節點控制在一個page大小，就可以保證，磁盤一次的查找只需要一次IO。一個page大小一般在4k，可以存儲不少的數據， 假設一個節點存儲數據量為100**，**深度為3的B-樹，即可保存100w數據(100*100*100)，而100的數據一般用不了4k的存儲空間。當然，這里節點中存儲的東西主要包括data和指針，指針大小是固定的，而數據有大有小。只要控制好每個數據塊的大小，就可以提高B-樹的性能。另外，一般情況下非葉子節點占用空間一般較小，完全可以緩存至內存中，這點也是在實際數據庫實現中常常使用到的優化。 ### B+樹  ### 特點 1. 有n棵子樹的節點中含有n個關鍵字。 1. 所有的葉子結點中包含了全部關鍵字的信息，及所指向含這些關鍵字記錄的指針，且葉子節點本身依關鍵字的大小而自小到大的順序鏈接。 1. 所有非葉子結點可以看成是索引部分，結點中僅含有其子樹中的最大(最小)關鍵字。 ### NOTE 1. B+樹通常有兩個指針，一個指向根結點，另一個指向關鍵字最小的葉子結點。因些，對于B+樹進行查找兩種運算：一種是從最小關鍵字起順序查找，另一種是從根結點開始進行隨機查找。 1. ?在隨機查找時，若非終端結點上的數據等于給定值，并不終止，而是繼續向下直到葉子結點。因此，在B+樹中，不管查找成功與否，每次查找都是走了一條從根到葉子結點的路徑 1. B+樹的查找與刪除都從葉子節點開始 1. B+樹的內部結點并沒有指向關鍵字具體信息的指針。因此其內部結點相對B 樹更小。如果把所有同一內部結點的關鍵字存放在同一盤塊中，那么盤塊所能容納的關鍵字數量也越多。一次性讀入內存中的需要查找的關鍵字也就越多。相對來說IO讀寫次數也就降低了 ### 應用場景： 這個結構一般用于數據庫的索引，綜合效率非常高，像 BerkerlyDB , sqlite , mysql 數據庫都使用了這個算法處理索引。如果想自己做個小型數據庫，可能參考一下這個算法的實現。索引在數據庫中的作用。在數據庫系統的使用過程當中，數據的查詢是使用最頻繁的一種數據操作。當數據庫中數據非常多的時候，數據查詢的效率就是數據庫系統用戶最關心的問題。要提高數據查詢的效率，最簡單、有效的方法就是在數據表相應的列上建立索引。索引是對數據庫表中一個或多個列的值進行排序的結構。與在表中搜索所有的行相比，索引用指針指向存儲在表中指定列的數據值，然后根據指定的次序排列這些指針，有助于更快地獲取信息。通常情況下，只有當經常查詢索引列中的數據時，才需要在表上創建索引。索引將占用磁盤空間，并且影響數據更新的速度。但是在多數情況下，索引所帶來的數據檢索速度優勢大大超過它的不足之處。 ### B+樹和B-樹最大的不同點 1. B-樹的關鍵字和記錄是放在一起的，葉子節點可以看作外部節點，不包含任何信息；B+樹的非葉子節點中只有關鍵字和指向下一個節點的索引，記錄只放在葉子節點中。 1. 在B-樹中，越靠近根節點的記錄查找時間越快，只要找到關鍵字即可確定記錄的存在；而B+樹中每個記錄的查找時間基本是一樣的，都需要從根節點走到葉子節點，而且在葉子節點中還要再比較關鍵字。從這個角度看B-樹的性能好像要比B+樹好，而在實際應用中卻是B+樹的性能要好些。因為B+樹的非葉子節點不存放實際的數據，這樣每個節點可容納的元素個數比B-樹多，樹高比B-樹小，這樣帶來的好處是減少磁盤訪問次數。盡管B+樹找到一個記錄所需的比較次數要比B-樹多，但是一次磁盤訪問的時間相當于成百上千次內存比較的時間，因此實際中B+樹的性能可能還會好些，而且B+樹的葉子節點使用指針連接在一起，方便順序遍歷(例如查看一個目錄下的所有文件，一個表中的所有記錄等)，這也是很多數據庫和文件系統使用B+樹的緣故。 數據庫中集中索引方式。比如一個數據庫中存儲的是：用戶信息(id, age, last_name, hometow)這樣的四元組 **hash index：**如果要查詢”finding all people with a last name of 'Smith.'”, 可以構造hash表，其key為last_name,而其value為指向某行的指針(也就是整條用戶信息)。但是如果要查詢"Find all people who are younger than 45."則hash表無能為力了，因為Hashes can deal with equality but not inequality. **bitmap index:**采用這種索引的話，查詢效率很高，可以在常數時間內查詢，但需要很大的存儲空間 **B- index:** The main benefit of a B-tree is that it **allows logarithmic selections, insertions, and deletions in the worst case scenario**.**And unlike hash indexes it stores the data in an ordered way, allowing for faster row retrieval when the selection conditions include things like inequalities or prefixes. **Nodes in a B-tree contain**a value **and **a number of pointers to children nodes.**For database indexes the "**value" is really a pair of values: the indexed field and a pointer to a database row.(but in B+ the value is only an indexed field)**That is,rather than storing the row data right in the index, you store a pointer to the row on disk. B-tree indexes are typically designed so that each node takes up one disk block?[](http://en.wikipedia.org/wiki/Block_(data_storage)). This allows each node to be read in with a single disk operation. ### 小結 B樹：平衡二叉樹，每個結點只存儲一個關鍵字，等于則命中，小于走左結點，大于走右結點； B-樹：多路搜索樹，每個結點存儲M/2到M個關鍵字，非葉子結點存儲指向關鍵字范圍的子結點； 所有關鍵字在整顆樹中出現，且只出現一次，非葉子結點可以命中； B+樹：在B-樹基礎上，為葉子結點增加鏈表指針，所有關鍵字都在葉子結點中出現，非葉子結點作為葉子結點的索引；B+樹總是到葉子結點才命中； 轉載請注明出處：[http://blog.csdn.net/songzitea/article/details/8864192](http://blog.csdn.net/songzitea/article/details/8864192)