B树、B-树、B+树、B*树【转】,mysql索引
B樹
???????即二叉搜索樹：
?????? 1.所有非葉子結點至多擁有兩個兒子（Left和Right）；
?????? 2.所有結點存儲一個關鍵字；
?????? 3.非葉子結點的左指針指向小于其關鍵字的子樹，右指針指向大于其關鍵字的子樹；
???????如：
???????
?????? B樹的搜索，從根結點開始，如果查詢的關鍵字與結點的關鍵字相等，那么就命中；
否則，如果查詢關鍵字比結點關鍵字小，就進入左兒子；如果比結點關鍵字大，就進入
右兒子；如果左兒子或右兒子的指針為空，則報告找不到相應的關鍵字；
???????如果B樹的所有非葉子結點的左右子樹的結點數目均保持差不多（平衡），那么B樹
的搜索性能逼近二分查找；但它比連續內存空間的二分查找的優點是，改變B樹結構
（插入與刪除結點）不需要移動大段的內存數據，甚至通常是常數開銷；
???????如：
??????
???但B樹在經過多次插入與刪除后，有可能導致不同的結構：
?
?? 右邊也是一個B樹，但它的搜索性能已經是線性的了；同樣的關鍵字集合有可能導致不同的
樹結構索引；所以，使用B樹還要考慮盡可能讓B樹保持左圖的結構，和避免右圖的結構，也就
是所謂的“平衡”問題；??????
???????實際使用的B樹都是在原B樹的基礎上加上平衡算法，即“平衡二叉樹”；如何保持B樹
結點分布均勻的平衡算法是平衡二叉樹的關鍵；平衡算法是一種在B樹中插入和刪除結點的
策略；
?
?
B-樹
???????是一種多路搜索樹（并不是二叉的）：
?????? 1.定義任意非葉子結點最多只有M個兒子；且M>2；
?????? 2.根結點的兒子數為[2, M]；
?????? 3.除根結點以外的非葉子結點的兒子數為[M/2, M]；
?????? 4.每個結點存放至少M/2-1（取上整）和至多M-1個關鍵字；（至少2個關鍵字）
?????? 5.非葉子結點的關鍵字個數=指向兒子的指針個數-1；
?????? 6.非葉子結點的關鍵字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
?????? 7.非葉子結點的指針：P[1], P[2], …, P[M]；其中P[1]指向關鍵字小于K[1]的
子樹，P[M]指向關鍵字大于K[M-1]的子樹，其它P[i]指向關鍵字屬于(K[i-1], K[i])的子樹；
?????? 8.所有葉子結點位于同一層；
???????如：（M=3）
?????? B-樹的搜索，從根結點開始，對結點內的關鍵字（有序）序列進行二分查找，如果
命中則結束，否則進入查詢關鍵字所屬范圍的兒子結點；重復，直到所對應的兒子指針為
空，或已經是葉子結點；
B-樹的特性：
?????? 1.關鍵字集合分布在整顆樹中；
?????? 2.任何一個關鍵字出現且只出現在一個結點中；
?????? 3.搜索有可能在非葉子結點結束；
?????? 4.其搜索性能等價于在關鍵字全集內做一次二分查找；
?????? 5.自動層次控制；
???????由于限制了除根結點以外的非葉子結點，至少含有M/2個兒子，確保了結點的至少
利用率，其最底搜索性能為：
????
???????其中，M為設定的非葉子結點最多子樹個數，N為關鍵字總數；
???????所以B-樹的性能總是等價于二分查找（與M值無關），也就沒有B樹平衡的問題；
???????由于M/2的限制，在插入結點時，如果結點已滿，需要將結點分裂為兩個各占
M/2的結點；刪除結點時，需將兩個不足M/2的兄弟結點合并；
?
?
B+樹
?????? B+樹是B-樹的變體，也是一種多路搜索樹：
?????? 1.其定義基本與B-樹同，除了：
?????? 2.非葉子結點的子樹指針與關鍵字個數相同；
?????? 3.非葉子結點的子樹指針P[i]，指向關鍵字值屬于[K[i], K[i+1])的子樹
（B-樹是開區間）；
?????? 5.為所有葉子結點增加一個鏈指針；
?????? 6.所有關鍵字都在葉子結點出現；
???????如：（M=3）
???B+的搜索與B-樹也基本相同，區別是B+樹只有達到葉子結點才命中（B-樹可以在
非葉子結點命中），其性能也等價于在關鍵字全集做一次二分查找；
?????? B+的特性：
?????? 1.所有關鍵字都出現在葉子結點的鏈表中（稠密索引），且鏈表中的關鍵字恰好
是有序的；
?????? 2.不可能在非葉子結點命中；
?????? 3.非葉子結點相當于是葉子結點的索引（稀疏索引），葉子結點相當于是存儲
（關鍵字）數據的數據層；
?????? 4.更適合文件索引系統；
??
B*樹
???????是B+樹的變體，在B+樹的非根和非葉子結點再增加指向兄弟的指針；
???B*樹定義了非葉子結點關鍵字個數至少為(2/3)*M，即塊的最低使用率為2/3
（代替B+樹的1/2）；
?????? B+樹的分裂：當一個結點滿時，分配一個新的結點，并將原結點中1/2的數據
復制到新結點，最后在父結點中增加新結點的指針；B+樹的分裂只影響原結點和父
結點，而不會影響兄弟結點，所以它不需要指向兄弟的指針；
?????? B*樹的分裂：當一個結點滿時，如果它的下一個兄弟結點未滿，那么將一部分
數據移到兄弟結點中，再在原結點插入關鍵字，最后修改父結點中兄弟結點的關鍵字
（因為兄弟結點的關鍵字范圍改變了）；如果兄弟也滿了，則在原結點與兄弟結點之
間增加新結點，并各復制1/3的數據到新結點，最后在父結點增加新結點的指針；
???????所以，B*樹分配新結點的概率比B+樹要低，空間使用率更高；
??
小結
?????? B樹：二叉樹，每個結點只存儲一個關鍵字，等于則命中，小于走左結點，大于
走右結點；
?????? B-樹：多路搜索樹，每個結點存儲M/2到M個關鍵字，非葉子結點存儲指向關鍵
字范圍的子結點；
???????所有關鍵字在整顆樹中出現，且只出現一次，非葉子結點可以命中；
?????? B+樹：在B-樹基礎上，為葉子結點增加鏈表指針，所有關鍵字都在葉子結點
中出現，非葉子結點作為葉子結點的索引；B+樹總是到葉子結點才命中；
?????? B*樹：在B+樹基礎上，為非葉子結點也增加鏈表指針，將結點的最低利用率
從1/2提高到2/3；
?
mysql中的索引
mysql中普遍使用B+Tree做索引，但在實現上又根據聚簇索引和非聚簇索引而不同
聚簇索引
所謂聚簇索引，就是指主索引文件和數據文件為同一份文件，聚簇索引主要用在Innodb存儲引擎中。在該索引實現方式中B+Tree的葉子節點上的data就是數據本身，key為主鍵，如果是一般索引的話，data便會指向對應的主索引，如下圖所示：
在B+Tree的每個葉子節點增加一個指向相鄰葉子節點的指針，就形成了帶有順序訪問指針的B+Tree。做這個優化的目的是為了提高區間訪問的性能，例如圖4中如果要查詢key為從18到49的所有數據記錄，當找到18后，只需順著節點和指針順序遍歷就可以一次性訪問到所有數據節點，極大提到了區間查詢效率。
非聚簇索引
非聚簇索引就是指B+Tree的葉子節點上的data，并不是數據本身，而是數據存放的地址。主索引和輔助索引沒啥區別，只是主索引中的key一定得是唯一的。主要用在MyISAM存儲引擎中，如下圖：
非聚簇索引比聚簇索引多了一次讀取數據的IO操作，所以查找性能上會差。
MyisAM索引與InnoDB索引相比較
- MyisAM支持全文索引（FULLTEXT）、壓縮索引，InnoDB不支持；
- InnoDB支持事務，MyisAM不支持；
- MyisAM順序儲存數據，索引葉子節點保存對應數據行地址，輔助索引很主鍵索引相差無幾；InnoDB主鍵節點同時保存數據行，其他輔助索引保存的是主鍵索引的值；
- MyisAM鍵值分離，索引載入內存（key_buffer_size），數據緩存依賴操作系統；InnoDB鍵值一起保存，索引與數據一起載入InnoDB緩沖池；MyisAM主鍵（唯一）索引按升序來存儲存儲，InnoDB則不一定
- MyisAM索引的基數值（Cardinality，show index?命令可以看見）是精確的，InnoDB則是估計值。這里涉及到信息統計的知識，MyisAM統計信息是保存磁盤中，在alter表或Analyze table操作更新此信息，而InnoDB則是在表第一次打開的時候估計值保存在緩存區內；
- MyisAM處理字符串索引時用增量保存的方式，如第一個索引是‘preform’，第二個是‘preformence’，則第二個保存是‘7，ance’，這個明顯的好處是縮短索引，但是缺陷就是不支持倒序提取索引，必須順序遍歷獲取索引
為什么選用B+/-Tree
一般來說，索引本身也很大，不可能全部存儲在內存中，因此索引往往以索引文件的形式存儲的磁盤上。這樣的話，索引查找過程中就要產生磁盤I/O消耗，相對于內存存取，I/O存取的消耗要高幾個數量級，所以評價一個數據結構作為索引的優劣最重要的指標就是在查找過程中磁盤I/O操作次數的漸進復雜度。換句話說，索引的結構組織要盡量減少查找過程中磁盤I/O的存取次數。
簡單點說說內存讀取，內存是由一系列的存儲單元組成的，每個存儲單元存儲固定大小的數據，且有一個唯一地址。當需要讀內存時，將地址信號放到地址總線上傳給內存，內存解析信號并定位到存儲單元，然后把該存儲單元上的數據放到數據總線上，回傳。
寫內存時，系統將要寫入的數據和單元地址分別放到數據總線和地址總線上，內存讀取兩個總線的內容，做相應的寫操作。
內存存取效率，跟次數有關，先讀取A數據還是后讀取A數據不會影響存取效率。而磁盤存取就不一樣了，磁盤I/O涉及機械操作。磁盤是由大小相同且同軸的圓形盤片組成，磁盤可以轉動(各個磁盤須同時轉動)。磁盤的一側有磁頭支架，磁頭支架固定了一組磁頭，每個磁頭負責存取一個磁盤的內容。磁頭不動，磁盤轉動，但磁臂可以前后動，用于讀取不同磁道上的數據。磁道就是以盤片為中心劃分出來的一系列同心環(如圖標紅那圈)。磁道又劃分為一個個小段，叫扇區，是磁盤的最小存儲單元。
磁盤讀取時，系統將數據邏輯地址傳給磁盤，磁盤的控制電路會解析出物理地址，即哪個磁道哪個扇區。于是磁頭需要前后移動到對應的磁道，消耗的時間叫尋道時間，然后磁盤旋轉將對應的扇區轉到磁頭下，消耗的時間叫旋轉時間。所以，適當的操作順序和數據存放可以減少尋道時間和旋轉時間。
為了盡量減少I/O操作，磁盤讀取每次都會預讀，大小通常為頁的整數倍。即使只需要讀取一個字節，磁盤也會讀取一頁的數據(通常為4K)放入內存，內存與磁盤以頁為單位交換數據。因為局部性原理認為，通常一個數據被用到，其附近的數據也會立馬被用到。
B-Tree：如果一次檢索需要訪問4個節點，數據庫系統設計者利用磁盤預讀原理，把節點的大小設計為一個頁，那讀取一個節點只需要一次I/O操作，完成這次檢索操作，最多需要3次I/O(根節點常駐內存)。數據記錄越小，每個節點存放的數據就越多，樹的高度也就越小，I/O操作就少了，檢索效率也就上去了。
B+Tree：非葉子節點只存key，大大滴減少了非葉子節點的大小，那么每個節點就可以存放更多的記錄，樹更矮了，I/O操作更少了。所以B+Tree擁有更好的性能。
總結
以上是生活随笔為你收集整理的B树、B-树、B+树、B*树【转】,mysql索引的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： flash builder eclips
- 下一篇： RDIFramework.NET ━ .