B-Tree是一種多路搜索樹（并不是二叉的）：
1.定義任意非葉子結(jié)點最多只有M個兒子氓奈；且M>2圈盔；
2.根結(jié)點的兒子數(shù)為[2, M]悲幅；
3.除根結(jié)點以外的非葉子結(jié)點的兒子數(shù)為[M/2, M]捕虽；
4.每個結(jié)點存放至少M/2-1（取上整）和至多M-1個關(guān)鍵字蜜自；（至少2個關(guān)鍵字）
5.非葉子結(jié)點的關(guān)鍵字個數(shù)=指向兒子的指針個數(shù)-1；
6.非葉子結(jié)點的關(guān)鍵字：K[1], K[2], …, K[M-1]司澎；且K[i] < K[i+1]欺缘；
7.非葉子結(jié)點的指針：P[1], P[2], …, P[M]；其中P[1]指向關(guān)鍵字小于K[1]的子樹挤安，P[M]指向關(guān)鍵字大于K[M-1]的子樹谚殊，其它P[i]指向關(guān)鍵字屬于(K[i-1], K[i])的子樹；
8.所有葉子結(jié)點位于同一層蛤铜；
如：（M=3）
B-樹的特性：
1.關(guān)鍵字集合分布在整顆樹中嫩絮；
2.任何一個關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個結(jié)點中；
3.搜索有可能在非葉子結(jié)點結(jié)束围肥；
4.其搜索性能等價于在關(guān)鍵字全集內(nèi)做一次二分查找剿干；
5.自動層次控制；
B-樹的搜索穆刻，從根結(jié)點開始置尔，對結(jié)點內(nèi)的關(guān)鍵字（有序）序列進行二分查找，如果命中則結(jié)束氢伟，否則進入查詢關(guān)鍵字所屬范圍的兒子結(jié)點撰洗；重復，直到所對應(yīng)的兒子指針為空腐芍，或已經(jīng)是葉子結(jié)點差导；關(guān)注、轉(zhuǎn)發(fā)猪勇、評論頭條號每天分享java知識设褐，私信回復“555”贈送一些Dubbo、Redis、Netty助析、zookeeper犀被、Spring cloud、分布式資料
B+樹是B-樹的變體外冀，也是一種多路搜索樹：
1.其定義基本與B-樹同寡键，除了：
2.非葉子結(jié)點的子樹指針與關(guān)鍵字個數(shù)相同；
3.非葉子結(jié)點的子樹指針P[i]雪隧，指向關(guān)鍵字值屬于[K[i], K[i+1])的子樹（B-樹是開區(qū)間）西轩；
5.為所有葉子結(jié)點增加一個鏈指針；
6.所有關(guān)鍵字都在葉子結(jié)點出現(xiàn)脑沿；
如：（M=3）
B+的搜索與B-樹也基本相同藕畔，區(qū)別是B+樹只有達到葉子結(jié)點才命中（B-樹可以在非葉子結(jié)點命中），其性能也等價于在關(guān)鍵字全集做一次二分查找庄拇；
B+的特性：
1.所有關(guān)鍵字都出現(xiàn)在葉子結(jié)點的鏈表中（稠密索引）注服，且鏈表中的關(guān)鍵字恰好是有序的；
2.不可能在非葉子結(jié)點命中措近；
3.非葉子結(jié)點相當于是葉子結(jié)點的索引（稀疏索引）溶弟，葉子結(jié)點相當于是存儲（關(guān)鍵字）數(shù)據(jù)的數(shù)據(jù)層；
4.更適合文件索引系統(tǒng)瞭郑；
mysql中的索引
mysql中普遍使用B+Tree做索引辜御，但在實現(xiàn)上又根據(jù)聚簇索引和非聚簇索引而不同。
聚簇索引
所謂聚簇索引凰浮，就是指主索引文件和數(shù)據(jù)文件為同一份文件我抠，聚簇索引主要用在Innodb存儲引擎中苇本。在該索引實現(xiàn)方式中B+Tree的葉子節(jié)點上的data就是數(shù)據(jù)本身袜茧，key為主鍵，如果是一般索引的話瓣窄，data便會指向?qū)?yīng)的主索引笛厦，如下圖所示：
在B+Tree的每個葉子節(jié)點增加一個指向相鄰葉子節(jié)點的指針，就形成了帶有順序訪問指針的B+Tree俺夕。做這個優(yōu)化的目的是為了提高區(qū)間訪問的性能裳凸，例如圖4中如果要查詢key為從18到49的所有數(shù)據(jù)記錄，當找到18后劝贸，只需順著節(jié)點和指針順序遍歷就可以一次性訪問到所有數(shù)據(jù)節(jié)點姨谷，極大提到了區(qū)間查詢效率。
非聚簇索
非聚簇索引就是指B+Tree的葉子節(jié)點上的data映九，并不是數(shù)據(jù)本身梦湘，而是數(shù)據(jù)存放的地址。主索引和輔助索引沒啥區(qū)別，只是主索引中的key一定得是唯一的捌议。主要用在MyISAM存儲引擎中哼拔，如下圖：
非聚簇索引比聚簇索引多了一次讀取數(shù)據(jù)的IO操作，所以查找性能上會差瓣颅。
MyisAM索引與InnoDB索引相比較
MyisAM支持全文索引（FULLTEXT）倦逐、壓縮索引，InnoDB不支持宫补；
InnoDB支持事務(wù)檬姥，MyisAM不支持；
MyisAM順序儲存數(shù)據(jù)守谓，索引葉子節(jié)點保存對應(yīng)數(shù)據(jù)行地址穿铆，輔助索引很主鍵索引相差無幾；InnoDB主鍵節(jié)點同時保存數(shù)據(jù)行斋荞，其他輔助索引保存的是主鍵索引的值荞雏；
MyisAM鍵值分離，索引載入內(nèi)存（key_buffer_size）平酿，數(shù)據(jù)緩存依賴操作系統(tǒng)凤优；InnoDB鍵值一起保存，索引與數(shù)據(jù)一起載入InnoDB緩沖池蜈彼；MyisAM主鍵（唯一）索引按升序來存儲存儲筑辨，InnoDB則不一定
MyisAM索引的基數(shù)值（Cardinality，show index 命令可以看見）是精確的幸逆，InnoDB則是估計值棍辕。這里涉及到信息統(tǒng)計的知識，MyisAM統(tǒng)計信息是保存磁盤中还绘，在alter表或Analyze table操作更新此信息楚昭，而InnoDB則是在表第一次打開的時候估計值保存在緩存區(qū)內(nèi)；
MyisAM處理字符串索引時用增量保存的方式拍顷，如第一個索引是‘preform’抚太，第二個是‘preformence’，則第二個保存是‘7昔案，ance’尿贫，這個明顯的好處是縮短索引，但是缺陷就是不支持倒序提取索引踏揣，必須順序遍歷獲取索引
為什么選用B+/-Tree
一般來說庆亡，索引本身也很大，不可能全部存儲在內(nèi)存中捞稿，因此索引往往以索引文件的形式存儲的磁盤上又谋。這樣的話钝尸，索引查找過程中就要產(chǎn)生磁盤I/O消耗，相對于內(nèi)存存取搂根，I/O存取的消耗要高幾個數(shù)量級珍促，所以評價一個數(shù)據(jù)結(jié)構(gòu)作為索引的優(yōu)劣最重要的指標就是在查找過程中磁盤I/O操作次數(shù)的漸進復雜度。換句話說剩愧，索引的結(jié)構(gòu)組織要盡量減少查找過程中磁盤I/O的存取次數(shù)猪叙。
簡單點說說內(nèi)存讀取，內(nèi)存是由一系列的存儲單元組成的仁卷，每個存儲單元存儲固定大小的數(shù)據(jù)穴翩，且有一個唯一地址。當需要讀內(nèi)存時锦积，將地址信號放到地址總線上傳給內(nèi)存芒帕，內(nèi)存解析信號并定位到存儲單元，然后把該存儲單元上的數(shù)據(jù)放到數(shù)據(jù)總線上丰介，回傳背蟆。
寫內(nèi)存時，系統(tǒng)將要寫入的數(shù)據(jù)和單元地址分別放到數(shù)據(jù)總線和地址總線上哮幢，內(nèi)存讀取兩個總線的內(nèi)容带膀，做相應(yīng)的寫操作。
內(nèi)存存取效率橙垢，跟次數(shù)有關(guān)垛叨，先讀取A數(shù)據(jù)還是后讀取A數(shù)據(jù)不會影響存取效率。而磁盤存取就不一樣了柜某，磁盤I/O涉及機械操作嗽元。磁盤是由大小相同且同軸的圓形盤片組成，磁盤可以轉(zhuǎn)動(各個磁盤須同時轉(zhuǎn)動)喂击。磁盤的一側(cè)有磁頭支架剂癌，磁頭支架固定了一組磁頭，每個磁頭負責存取一個磁盤的內(nèi)容惭等。磁頭不動珍手，磁盤轉(zhuǎn)動办铡，但磁臂可以前后動辞做，用于讀取不同磁道上的數(shù)據(jù)。磁道就是以盤片為中心劃分出來的一系列同心環(huán)(如圖標紅那圈)寡具。磁道又劃分為一個個小段秤茅，叫扇區(qū)，是磁盤的最小存儲單元童叠。
磁盤讀取時框喳，系統(tǒng)將數(shù)據(jù)邏輯地址傳給磁盤课幕，磁盤的控制電路會解析出物理地址，即哪個磁道哪個扇區(qū)五垮。于是磁頭需要前后移動到對應(yīng)的磁道乍惊，消耗的時間叫尋道時間，然后磁盤旋轉(zhuǎn)將對應(yīng)的扇區(qū)轉(zhuǎn)到磁頭下放仗，消耗的時間叫旋轉(zhuǎn)時間润绎。所以，適當?shù)牟僮黜樞蚝蛿?shù)據(jù)存放可以減少尋道時間和旋轉(zhuǎn)時間诞挨。
為了盡量減少I/O操作莉撇，磁盤讀取每次都會預讀，大小通常為頁的整數(shù)倍惶傻。即使只需要讀取一個字節(jié)棍郎，磁盤也會讀取一頁的數(shù)據(jù)(通常為4K)放入內(nèi)存，內(nèi)存與磁盤以頁為單位交換數(shù)據(jù)银室。因為局部性原理認為涂佃，通常一個數(shù)據(jù)被用到，其附近的數(shù)據(jù)也會立馬被用到蜈敢。
B-Tree：如果一次檢索需要訪問4個節(jié)點巡李，數(shù)據(jù)庫系統(tǒng)設(shè)計者利用磁盤預讀原理，把節(jié)點的大小設(shè)計為一個頁扶认，那讀取一個節(jié)點只需要一次I/O操作侨拦，完成這次檢索操作，最多需要3次I/O(根節(jié)點常駐內(nèi)存)辐宾。數(shù)據(jù)記錄越小狱从，每個節(jié)點存放的數(shù)據(jù)就越多，樹的高度也就越小叠纹，I/O操作就少了季研，檢索效率也就上去了。
B+Tree：非葉子節(jié)點只存key誉察，大大滴減少了非葉子節(jié)點的大小与涡，那么每個節(jié)點就可以存放更多的記錄，樹更矮了持偏，I/O操作更少了驼卖。所以B+Tree擁有更好的性能。
