文章是學習了林曉斌老師在極客時間的《mysql實戰45講》后，根據自己的理解整理而成的。
當我們使用漢語字典查找某個字時，我們會先通過拼音目錄查到那個字所在的頁碼，然后直接翻到字典的那一頁，找到我們要查的字，通過拼音目錄查找比我們拿起字典從頭一頁一頁翻找要快的多，數據庫索引也一樣，索引就像書的目錄，通過索引能極大提高數據查詢的效率。
在數據庫中，常見的索引實現方式有哈希表、有序數組、搜索樹
二叉搜索樹：一棵空樹，或者是具有下列性質的二叉樹： 若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值； 若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值； 二叉搜索樹的左、右子樹也分別為二叉搜索樹。
平衡二叉樹：平衡二叉樹是在二叉搜索樹的基礎上引入的，指的是結點的左子樹和右子樹的深度差不超過1.
多叉樹：每個結點可以有多個子結點，子節點的大小從左到右依次遞增。
當使用平衡二叉實現索引時，結構如下圖
從圖中可發現，每次查詢最多需要訪問4個節點必能得到所要數據。例如查詢user2時，查詢過程為：userA-->userC-->userF-->user2。
所以查詢速度很高，同時，因為搜索樹的特性（左子樹小于右子樹），區間查詢也很方便。
<br>
如果搜索樹存于內存中，與多叉樹相比，二叉樹的搜索速率是最高的，但實際上數據庫使用的是n叉樹而不是二叉樹。
1、索引不僅存于內存，還是寫到磁盤上
2、搜索樹上的每個結點在磁盤上表現為一個數據塊
3、多叉樹每個結點下可以有多個子節點，所以存儲相同數據量時多叉樹的樹高比二叉樹小，查詢一個數據需要訪問的結點數更少，即查詢過程訪問更少的數據塊。查詢速度較高。
innodb使用B+樹作為索引結構。
在B+樹中，我們將節點分為葉子結點和非葉子結點，非葉子結點上保存的是索引，而且一個節點可以保存多個索引；數據全部存于葉子結點上,根據葉子結點的內容不同，innodb索引分為主鍵索引和非主鍵索引。非主鍵索引也稱為二級索引。
主鍵索引的葉子結點中保存的數據為整行數據，而非主鍵索引葉子節點保存的是主鍵的值。
主鍵索引圖
非主鍵索引圖
通過主鍵索引查詢數據時，我們只需查找主鍵索引樹便可以獲取數據；通過非主鍵索引查詢數據時，我們先通過非主鍵索引樹查找到主鍵值，然后再在主鍵索引樹搜索一次，這個過程稱為回表，也就是說非主鍵索引查詢會比主鍵查詢多搜索一棵樹。所以我們應盡可能使用主鍵查詢。
添加新行時，將會在索引表上添加一條記錄，如果是索引遞增插入時，數據都是追加在當前最大索引之后，不會對樹中其他數據造成影響；如果新加入的數據的索引值位于節點的中間，需要挪動部分節點的位置，從而保持索引樹的有序性。
而且，相鄰多個節點是存儲在同一個數據頁上的，此時，如果是在已經存儲滿狀態的數據頁中插入節點，會申請新的數據頁，將部分數據挪動到新的數據頁，這個過程稱為頁分裂，頁分裂除了會影響性能，還會降低磁盤空間利用率。不規則數據插入時,會造成頻繁的頁分裂。
當相鄰兩個頁由于刪除了數據，利用率很低之后，會將數據頁做合并
所以，一般情況下會采用遞增主鍵，使新數據遞增插入。
使用業務邏輯字段做主鍵有什么優缺點？
1、業務邏輯字段不容易保證索引樹結點有序插入，這樣寫入成本較高。
2、innodb默認使用整數類型作為主鍵，主鍵長度較小，二級索引的葉子結點中保存的是主鍵值，主鍵長度越小，二級索引的葉子結點占用空間也就越小。
3、當然，使用業務邏輯字段做主鍵也有好處，可以避免回表，每次只需掃描一次主鍵索引樹即可
綜上，從性能和存儲空間方面考量，自增主鍵往往是更合理的選擇,當業務場景有且只有一個索引，而且該索引為唯一索引時，此時更適合使用業務邏輯字段作為主鍵。
因為數據修改/刪除、頁分裂等原因，會導致數據頁空間利用率降低，此時，可以考慮重建索引，將數據按順序插入，提高磁盤空間利用率。但重建主鍵索引和普通索引會有不同影響，重建普通索引，可以達到提高空間利用率的目的，且不會對其他索引造成影響，但如果重建主鍵索引就不合理了，會影響所有普通索引，性能影響較大，而且無論是新建/刪除主鍵，都會重建整張表。這時我們可以使用alter table T engine=InnoDB這個語句代替。
查看索引利用率
查看performance_schema.table_io_waits_summary_by_index_usage表
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
