MySQL系列（三）——索引

前言：如果有疏忽或理解不當的地方，請指正。有關於數據結構的內容本文沒有詳細介紹，後續會在數據結構系列進行介紹。

目錄

• MySQL系列（一）：基礎知識大總結
• MySQL系列（二）：MySQL事務
• MySQL系列（三）：索引

什麼是索引

• 如果沒有索引，掃描的記錄數大於有索引的記錄數
• 索引存放索引列的值（比如id為索引列，那麼存放索引列的值），和該索引值對應的行在內存中的地址（或者直接存儲該行的數據）
• SELECT * FROM user WHERE username= "jiajun" ,username建立索引，如果索引採用的數據結構是hash表，那麼這個時候，通過計算jiajun的hash值，O（1）複雜度就可以找到該記錄的位置

hash索引

• 在等值查找下，此時無hash衝突，這種情況下，效率是很高的
• 但是在範圍查找下，由於hash不是有序的，那麼範圍查找下，hash表的優勢並不能發揮出來。
• 在hash衝突下，查找效率會降下來

磁碟讀取

• 磁碟讀取步驟：定柱面，定磁軌，定磁塊
• 磁碟時間主要消耗在定位柱面，那麼如果要提高速度，在數據量一樣的情況下，將盡量多的數據放在磁碟塊上，那麼這樣可以減少磁頭定位柱面移動的次數，減少IO的次數。

二叉查找樹

• 左子樹所有的節點的值小於他的根節點的值
• 右子樹所有的節點的值大於他的根節點的值
• 任意節點的左子樹和右子樹都是二叉查找樹
• 沒有鍵值相等的節點

分析

• 二叉查找樹的查找的複雜度到了lgn
• 但是有沒有辦法減少IO的次數，也就是能不能降低樹的高度

B-樹

（m階樹 m/2<=k<=m）

• 根節點至少兩個子節點
• 所有葉子節點都在同一層
• 中間節點包含k-1個元素和k個孩子
• 節點中的元素從小到大排列
• 每個節點即包含索引列的值，和該數據記錄（或該數據記錄的值）

分析

• 相對於二叉查找樹，B樹變得矮胖，因為每個節點存放的元素更多，所以相同元素情況下，降低了樹的高度，那麼就可以減少IO的次數
• 每個節點存放了數據（該行記錄的值或者該行記錄在內存的地址），所以不同的查詢性能是不一樣的。

B+樹

• 在B-樹的基礎上
• 除了葉子結點，其他節點不包含記錄（資料庫中的行）的位置
• 葉子節點包含了所有的索引值，並且從小到大排列，以及記錄（資料庫中行）的位置

分析

• 如果節點的大小一樣，那麼如果我們除了葉節點之外，其他節點不包含數據，那麼就可以放更多的元素（索引值），這樣的話這棵樹就變的更加矮胖，那麼IO的次數可以進一步減少
• 因為葉節點的元素是順序排列，而且葉節點間形成鏈表，那麼有序查找時提高範圍查詢的效率
• 相對於B樹，由於所有的數據是存放在葉節點，那麼意味著每次查找都必須到從根查找到葉節點，那麼這就意味著查詢性能平均。

總結

• 索引是一種數據，可以避免了全表查詢，可以類比目錄和書。
• 索引需要一種數據結構來存儲
• 利用散列表（hash）的方式查詢複雜度可以到O（1），但是再範圍查詢時，hash起不了提高性能的作用
• IO操作是耗時，為了提高查詢性能，可以減少IO的次數
• 對於樹的存儲結構來說，為了提高性能，減少IO的次數，可以低樹的高度
• 讀取一個節點一次IO，在數據量一樣的情況下，如果每個節點的能存放更多元素，那麼就可以降低樹的高度。
• B樹降低了樹的高度，而在節點大小一樣的情況下，因為B樹的節點存放了元素有又存放了數據，而B+樹將數據全部存放在葉節點，那麼這樣的話，每個節點可以存放更多的元素，那麼就可以再一次降低樹的高度
• B+樹的查詢性能更加穩定，並且更有利於範圍查找
• 如果是聚集索引（InnoDB引擎），那麼節點存放的該記錄的數據，數據文件本身就是索引文件
• 如果是非聚集索引（MyISAM引擎），那麼節點存放的是該行記錄的地址。索引文件和數據文件是分離

索引的種類

• 普通索引，允許出現相同的內容
• 唯一索引，索引值唯一，允許空值
• 主鍵索引，創建主鍵的時候自動創建主鍵索引，唯一併且不能為空
• 組合索引，多列組合索引

索引的使用

• ALTER TABLE table_name ADD INDEX index_name (column_list) 增加普通索引
• ALTER TABLE table_name ADD UNIQUE (column_list) 增加唯一索引
• ALTER TABLE table_name ADD PRIMARY KEY (column_list) 增加主鍵索引

索引優缺點

• 毫無疑問，在使用正確的情況下，索引能提高查詢速度
• 索引也能提高分組和排序的速度
• 由於修改刪除添加時，要調維護索引文件，對樹進行調整，所以性能降低了
• 索引文件也是需要佔用空間的

我覺得分享是一種精神，分享是我的樂趣所在，不是說我覺得我講得一定是對的，我講得可能很多是不對的，但是我希望我講的東西是我人生的體驗和思考，是給很多人反思，也許給你一秒鐘、半秒鐘，哪怕說一句話有點道理，引發自己內心的感觸，這就是我最大的價值。（這是我喜歡的一句話，也是我寫博客的初衷）

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！