mysql總結筆記 -- 索引篇

索引的作用

索引是用來高效的獲取數據的 排好序 的 數據結構，如果沒有索引，可能會導致查詢某一條記錄的時候遍歷整張表；所以適當的索引可以大大的提升檢索速度；

索引的數據結構

  • 二叉樹

假如說我們有一列數據是0-6，我們使用的是二叉樹進行存儲的話，此時我們可以看到二叉樹的存儲方式為下圖：

image

  • 我們可以看到二叉樹如同鏈表的形式存儲了完整的數據，這時我們假設要查值為6的數據，我們就需要七次IO操作才能拿到數據結果；試想假如我們數據過多這時候查詢數據就會非常的慢，就相當於全表掃描；
  • 所以我們的mysql資料庫，肯定是不會用這種數據結構來存儲數據；
  • 紅黑樹
    image
  • 同樣是的存儲數據0-6，這時我們會發現紅黑樹在每次存儲的時候，都會動一下；目的就是為了平衡，本質上和二叉樹是一樣的這裡只是多了一步平衡操作，所以紅黑樹又稱平衡二叉樹；
  • 在查詢上我們也可以看到，相比於二叉樹來說它做了平衡，樹層級相對來說會變小，在我們查找數據的時候IO操作也相對來說少些了；
  • mysql也沒用這種數據結構，其實我們也應該想的到，一方面數據多了節點一直往下分散還是可能會很多；另一個方面每變動一個節點的時候樹都會做平衡花銷不可估量；
  • hash表

hash 我們知道查找數據的複雜度為O(1)
image

  • 對索引的key進行一次hash計算就可以定位出數據的存儲位置；
  • 很多時候hsah比b+tree更高效，因為只要hash到對應的key值就能拿到元素；
  • 只能滿足 "=", "in" 不能範圍查找；
  • 會存在hash衝突問題（如上圖key=2的數據，同一個key存儲了兩個值，在拿數據的時候會定位到2的數據，然後一次比對拿符合條件的數據）；
    因為本質的複雜度為O(1)特性速度一般會很快，但是我們工作中一般用的不是很多，最根本也是最重要的原因是不支援範圍查找，還存在hash衝突的問題；
  • b-tree
  • 通過上邊你的二叉樹紅黑樹我們可以發現都有個共同的問題，就是數據多了層級都會很深查數據都會很慢；這裡b-tree就做了一個改進，每個節點可以橫向擴展存更多的數據，這時樹的層級就會明顯變少，減少磁碟IO操作；如下圖：
    image
  • 上圖我們可以看到，節點橫向擴展可以存儲更多的節點數據, 也就是說一次IO操作我們可以那倒更多的數據，如果不存在時我們就進行下一個節點查詢; 我們也可以看到每個索引元素都同時存儲了data數據, 也就是說當我們找到索引是可以馬上拿到data的; 節點中的數據索引從左到右依次遞增；
  • mysql也不是用的這種數據結構，畢竟還是存在一些弊端如：
  1. 每個索引節點都存儲了data數據，每個節點的存儲空間有限，這時層級也會存在深的情況；
  2. 沒有相鄰的雙向指針，當範圍查找時都需要節點挨個篩選，不利於範圍查詢；
  3. 當我們發生修改刪除數據時，也會伴隨著樹節點的變動，從而造成性能上的損耗；
  • b+tree

mysql用的就是這種數據結構, 其實b+tree是b-tree的一個變種大概還是一樣做了些改進：

  1. 非葉子節點不存儲data數據, 只存儲索引，相比於b-tree可以放更多的索引；
  2. 葉子節點存有data和所有節點的索引欄位；
  3. 葉子節點之間用指針相連接，提升了區間訪問的性能；
  4. 節點中的索引從左到右依次遞增；
  5. 刪除數據時只刪除葉子節點，非葉子節點不變，不影響整個樹的結構；
    image

補充 樹中每個節點可以存儲16Kb的數據
可以用下方sql查詢

show GLOBAL STATUS like 'Innodb_page_size'

那我們來計算下每個節點大概能存儲多少數據：
image

假設我們用bigInt類型當自增主鍵的話，bigInt也就是上圖的索引元素佔8個位元組，磁碟地址指針mysql默認分配6個位元組；也就是說我們一個節點可以存儲16Kb/(8+6)B約等於1170個元素；葉子節點因為要存儲data元素所以元素個數可能會相對其他節點少，我們假設只存儲了15個元素，那麼我們一個三階的樹就可以存儲 1170117015 約 兩千萬條數據，也就是說兩千萬的數據我們只需要三次IO就能拿到值(mysql本身也有做優化非葉子節點會被載入到記憶體中，也就是說我們取值可能就一次IO就能拿到值，速度會大大提升)；

MyISAM 存儲引擎

MyISAM 存儲引擎中數據存儲分三個文件存儲分別為 .frm結構 .MYD數據 .MYI索引 三個文件，即為非聚集索引；
image
上圖我們可以看到索引和數據存在不同的文件中，當我們檢索數據的時候是先找MYI文件定位到引用地址，再去MYD中拿數據的；

InnoDB 存儲引擎

InnoDB 存儲引擎中數據和索引是放在同一個文件中分別為 .frm結構 .idb 兩個文件，即為 聚集索引；
image

  • InnoDB 中每個葉子節點存儲整條數據的所有欄位（如葉子節點索引18，存儲的是數據 77 Alice）；
  • 表文件本身就是一個b+tree樹組織的索引結構文件；
  • 由於主鍵和數據都在同一個文件中，所以InnoDB必須要有一個主鍵，並且建議為自增主鍵(如果不設主鍵則mysql會自動的在你的列表中找到一個符合條件的唯一索引欄位，如果沒有mysql將添加一個類似 ROW_Id 充當主鍵)；
  • 非主鍵索引結構的葉子節點存儲的是主鍵值，是為了實現一致性，節省存儲空間；
聚集索引和非聚集索引哪個效率更高

非聚集索引查詢到索引值之後，只是拿到了索引所在行的磁碟文件地址，需要通過這個地址再進行一次I/O操作;
聚集索引讀取到葉子節點索引值之後，即那到了索引所在行的完整的數據內容，不需要額外的I/O操作;

工具輔助

動圖樹模擬地址：//www.cs.usfca.edu/~galles/visualization/BST.html;
動圖製作工具：GifCam工具；

Tags:

VirMach 便宜 VPS