MySQL索引以及結構深入詳解

B-tree

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

B+tree

B+Tree是一種改進后的B-tree。
MySQL索引以及結構深入詳解
(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為主鍵。如下圖:
MySQL索引以及結構深入詳解
(t1表)
MySQL索引以及結構深入詳解
(t2表)
MySQL索引以及結構深入詳解
(數據庫對應的文件)
因為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)!

? 版權聲明
THE END
喜歡就支持一下吧
點贊7 分享