B-tree

B-Tree又叫平衡多路查找樹（并不是二叉的）使用B-tree結構可以顯著減少定位記錄時所經歷的中間過程，從而加快存取速度。
左子節點關鍵字值在B-Tree中按key檢索數據的算法非常直觀：首先從根節點進行二分查找，如果找到則返回對應節點的data，否則對相應區間的指針指向的節點遞歸進行查找，直到找到節點或找到null指針，前者查找成功，后者查找失敗。

（key為記錄的鍵值，對于不同數據記錄，key是互不相同的；data為數據記錄除key外的數據）

B+tree

B+Tree是一種改進后的B-tree。

（key為記錄的鍵值，對于不同數據記錄，key是互不相同的；data為數據記錄除key外的數據）

與B-Tree相比，B+Tree有以下不同點：

• 每個節點的指針上限為2d而不是2d+1。

• 內節點不存儲data，只存儲key；葉子節點不存儲指針。

那數據庫為什么使用B-tree

計算機的機械磁盤，為了攤還機械移動花費的等待時間，磁盤會一次存取多個數據項而不是一個，這樣的一次讀取的信息單元是page，我們可以用讀或寫的頁數作為磁盤存取總時間的主要近似值，在任何時刻，B樹算法都只需在內存中保持一定數量的頁面。B樹的設計考慮磁盤預讀取這點，一個B樹的節點通常和一個完整磁盤頁（page）一樣大，并且磁盤頁的大小限制了一個B樹節點可以含有的孩子個數（分支因子），當然這個具體也需要取決于一個關鍵字相對一頁的大小。

為了盡量減少I/O操作，磁盤讀取每次都會預讀，大小通常為頁的整數倍。即使只需要讀取一個字節，磁盤也會讀取一頁的數據(通常為4K)放入內存，內存與磁盤以頁為單位交換數據。因為局部性原理認為，通常一個數據被用到，其附近的數據也會立馬被用到。

B-Tree：如果一次檢索需要訪問4個節點，數據庫系統設計者利用磁盤預讀原理，把節點的大小設計為一個頁，那讀取一個節點只需要一次I/O操作，完成這次檢索操作，最多需要3次I/O(根節點常駐內存)。數據記錄越小，每個節點存放的數據就越多，樹的高度也就越小，I/O操作就少了，檢索效率也就上去了。

B+Tree：非葉子節點只存key，大大滴減少了非葉子節點的大小，那么每個節點就可以存放更多的記錄，樹更矮了，I/O操作更少了。所以B+Tree擁有更好的性能。

什么是索引

索引說白了就是一種數據結構。

索引的代價

索引也是有代價的：索引文件本身要消耗存儲空間，同時索引會加重插入、刪除和修改記錄時的負擔，另外，MySQL在運行時也要消耗資源維護索引，因此索引并不是越多越好。一般兩種情況下不建議建索引
第一種情況是表記錄比較少
另一種不建議建索引的情況是索引的選擇性較低。所謂索引的選擇性(Selectivity)，是指不重復的索引值(也叫基數，Cardinality)與表記錄數(#T)的比值

索引的類別

一、普通索引
二、唯一索引
三、主鍵索引
四、組合索引

MySQL中使用的索引

MySQL中普遍使用B+Tree做索引，但在實現上又根據聚簇索引和非聚簇索引而不同。

聚集索引與非聚集索引

所謂聚簇索引，就是指主索引文件和數據文件為同一份文件，聚簇索引主要用在Innodb存儲引擎中。在該索引實現方式中B+Tree的葉子節點上的data就是數據本身，key為主鍵。如下圖：

（t1表）

（t2表）

（數據庫對應的文件）
因為InnoDB的數據文件本身要按主鍵聚集，所以InnoDB要求表必須有主鍵（MyISAM可以沒有），如果沒有顯式指定，則MySQL系統會自動選擇一個可以唯一標識數據記錄的列作為主鍵，如果不存在這種列，則MySQL自動為InnoDB表生成一個隱含字段作為主鍵，這個字段長度為6個字節，類型為長整形。

MySQL數據庫中MyISAM和InnoDB數據存儲引擎

主要區別：
MyISAM是非事務安全型的，而InnoDB是事務安全型的。
MyISAM鎖的粒度是表級，而InnoDB支持行級鎖定。
MyISAM支持全文類型索引，而InnoDB不支持全文索引。
MyISAM相對簡單，所以在效率上要優于InnoDB，小型應用可以考慮使用MyISAM。
MyISAM表是保存成文件的形式，在跨平臺的數據轉移中使用MyISAM存儲會省去不少的麻煩。
InnoDB表比MyISAM表更安全，可以在保證數據不會丟失的情況下，切換非事務表到事務表（alter table tablename type=innodb）。
應用場景：
MyISAM管理非事務表。它提供高速存儲和檢索，以及全文搜索能力。如果應用中需要執行大量的SELECT查詢，那么MyISAM是更好的選擇。
InnoDB用于事務處理應用程序，具有眾多特性，包括ACID事務支持。如果應用中需要執行大量的INSERT或UPDATE操作，則應該使用InnoDB，這樣可以提高多用戶并發操作的性能。

補充

主存的存

取過程
當系統需要讀取主存時，則將地址信號放到地址總線上傳給主存，主存讀到地址信號后，解析信號并定位到指定存儲單元，然后將此存儲單元數據放到數據總線上，供其它部件讀取。
寫主存的過程類似，系統將要寫入單元地址和數據分別放在地址總線和數據總線上，主存讀取兩個總線的內容，做相應的寫操作。
這里可以看出，主存存取的時間僅與存取次數呈線性關系，因為不存在機械操作，兩次存取的數據的“距離”不會對時間有任何影響，例如，先取A0再取A1和先取A0再取D3的時間消耗是一樣的

磁盤存取原理

當需要從磁盤讀取數據時，系統會將數據邏輯地址傳給磁盤，磁盤的控制電路按照尋址邏輯將邏輯地址翻譯成物理地址，即確定要讀的數據在哪個磁道，哪個扇區。為了讀取這個扇區的數據，需要將磁頭放到這個扇區上方，為了實現這一點，磁頭需要移動對準相應磁道，這個過程叫做尋道，所耗費時間叫做尋道時間，然后磁盤旋轉將目標扇區旋轉到磁頭下，這個過程耗費的時間叫做旋轉時間。

?以上就是MySQL索引以及結構深入詳解的內容，更多相關內容請關注PHP中文網（www.php.cn）！