筆記記錄自林曉斌（丁奇）老師的《MySQL實戰45講》 4） --深入淺出索引（上） 一句話簡單來說，索引的出現其實就是為了提高數據查詢的效率，就像書的目錄一樣。 索引的常見模型 哈希表：哈希表是一種以Key-Value存儲數據的結構，只要輸入key，就可以找到對應的value。哈希的思路很簡單， ...
筆記記錄自林曉斌（丁奇）老師的《MySQL實戰45講》
4） --深入淺出索引（上）
一句話簡單來說，索引的出現其實就是為了提高數據查詢的效率，就像書的目錄一樣。
索引的常見模型
哈希表：哈希表是一種以Key-Value存儲數據的結構，只要輸入key，就可以找到對應的value。哈希的思路很簡單， 把值放在數組裡，有一個哈希函數把key換算成一個確定的位置，然後把value放在數組的這個位置。不可避免地多個key值經過hash計算可能會出現同一個值，處理這種情況的一種方法是，拉出一個鏈表。查找時先通過key計算hash值找到這個鏈表，然後按順序遍歷鏈表。需要註意的是，hash存儲的value並不是遞增的，所以哈希索引做區間查詢的速度很慢。所以，哈希表這種結構適用於只有等值查詢的場景。比如Memcached及其他一些NoSQL引擎。
有序數組：有序數組在等值查詢和範圍查詢場景中的性能都很優秀。如果僅僅看查詢效率，有序數組就是最好的數據結構了。但是，在需要更新數據時就很麻煩，在有序數組中間插入一個記錄，就必須挪動後面所有的記錄，成本太高。
二叉搜索樹：二叉搜索樹的特點是：每個節點的左兒子小於父節點，父節點又小於右兒子。當然為了維持O(log(N))的查詢複雜度，需要保證這棵樹是平衡二叉樹,為了保證是平衡二叉樹所做的操作的時間複雜度也是O(log(N))。樹可以有二叉，也可以有多叉。多叉樹保證兒子從左到右遞增。二叉樹是搜索效率最高的，但是實際上大多數資料庫存儲並不使用二叉樹。其原因是，索引不止存在於記憶體中，還要寫到磁碟上。N叉樹由於在讀寫性能上的優點，以及適配磁碟的訪問模式，已經被廣泛應用。以InnoDB為例，這個N的值差不多是1200.當樹高是4時，已經可以存儲17億左右的數據了。
InnoDB索引模型：
InnoDB使用了B+樹的索引模型。索引類型可以分為主鍵索引和非主鍵索引。
主鍵索引的葉子節點存儲的是整行數據。在InnoDB中，主鍵索引也被稱為聚簇索引（clustered index）
非主鍵索引的葉子節點內容是主鍵的值，在InnoDB中，非主鍵索引也被稱為二級索引（secondary index）
因此，基於主鍵索引和普通索引的查詢有很大的區別。如果使用主鍵索引ID來查詢，只需要搜索ID對應的B+樹。而如果使用非主鍵索引K來進行查詢，需要先搜索K索引樹，得到主鍵索引的值，再到主鍵索引樹種進行搜索。這個過程稱為回表。
索引維護：
B+樹為了維護索引有序性，在插入新值的時候，需要做必要的維護。如果可以直接插入到末尾就會直接插入，否則則需要邏輯上挪動後面的數據，空出位置來。而如果要插入的位置的數據頁已經滿了，根據B+樹的演算法，需要申請一個新的數據頁，然後挪動部分數據到新的頁上，這個過程稱為頁分裂。整體空間利用率及性能都會受到相應影響。當然有分裂也有合併，暫且不談了。基於以上索引維護內容，解釋了為什麼大多數建表語句都要求有自增主鍵。Not NULL PRIMARY KEY AUTO_INCREMENT。這樣每次操作都會是追加操作，直接插入到末尾。另外，如果使用別的有業務邏輯的欄位來做主鍵一是很難保證有序性。二來由於非主鍵索引儲存的是主鍵的值，如果用較長的欄位做主鍵，則普通索引葉子節點就會相應較大，普通索引所占用的空間也會變大。
當然事無絕對，在特定場景下也可能使用業務欄位做主鍵更合適。如：1.只有一個索引，2該索引是唯一索引。即典型的Key-Value場景。
上篇問題答案：
如果你是資料庫負責人，你有什麼方案來避免長事務呢？
從應用端來說：1.確認是否使用了 set autocommit=0，你應該保證這個值為1。2.確認是否有不必要的只讀事務。3業務連接資料庫時，根據業務本身的預估，通過 SET MAX_EXECUTION_TIME命令控制每個語句的最長執行時間。
從資料庫端來說： 1.監控 information_schema.Innodb_trx表，設置長事務閾值，超過就報警或kill掉。2.Percona的pt-kill工具不錯（這個筆者也不知道是什麼東東，感興趣可以搜一下）3.在業務功能的測試階段要求輸出所有general_log，分析日誌。4.如果使用的是MySQL5.6或更新版本，將innodb_undo_tablespaces設置成2（或更大的值），這樣即使真的回滾段過大，清理也更方便。（不明白）
問題：
對於普通索引k，重建時可以這麼寫：
alter table T drop index k; alter table T add Index(k);
對於主鍵索引，可以這麼寫：
alter table T drop primary key; alter table T add primary key(id);
對於上面的重建索引的作法，說出你的理解。如果有不合時的，為什麼?更好的作法是什麼？
