因為想要繼續成長，跳脫舒適圈，挑戰自己，所以近期投了蠻多履歷，也在不斷的面試，面試的職缺除了自己較擅長的Data Scientist之外，也有投了Data Engineer跟Backend Engineer，後兩者其實不是自己擅長的領域，是因為在檢視自己這兩年的成長和學習後，規劃的職涯技能養成，在這兩個職位，較有機會有更多的充實與精進，所以就硬著頭皮開始準備，包含系統設計、演算法刷題等等…。
好啦，有點扯遠了，扣回今天的主題，今天面試的時候，被問到了對於資料庫Index的理解，以及為甚麼需要Index時，很直覺的就回答了Index 用了B+ Tree的資料結構，並且建了索引之後，可以讓搜尋的速度加速等等，但等到問了Index的實際運作方式時，就直接卡住，也被面試官點醒，這是一個Backend Engineer非常需要知道的知識。
於是，心動不如馬上行動，立馬決定花一點時間，紀錄一下有關Index的學習，包含用途以及運作的原理，也順便幫助大家，之後遇到，可以更深入的回答Index的相關問題。
What is index?
資料庫索引，是資料庫管理系統中一個 排序的資料結構，以協助快速查詢、更新資料庫表中資料(Wiki)，這個資料結構中，包含了指向資料的指針，且這個索引結構是有序的。
以MySQL為例，如果沒有做任何設定，則默認的儲存引擎就是InnoDB，其索引的資料結構選用的就是B+ Tree，以下皆假設使用了B+ Tree作為索引結構，通常在設定完PK的時候，就會默認為PK欄位建立索引。
因為B+ Tree皆將資料保存在葉子節點(是一種聚集索引)，所以每一次的查找都需要從根節點找到葉子節點，因此時間複雜度基本等於樹高O(h)，也大抵為O(logN)。
後來找到了一個蠻酷的工具，他可以幫助你可視化資料結構，假如我們的Index是從1-10依序加入，單調遞增的話，在BST(Binary Search Tree) 、AVL、B Tree、B+ Tree三個資料結構各會長甚麼樣子呢
BST
我們可以觀察到，這棵樹雖然符合BST的規則，但幾乎變成Linked List的資料結構，變得相當不平衡，導致每次查找最差可能需要O(n)，為了解決這種不平衡的狀態，所以有了二叉平衡樹(AVL)的結構，會自動去平衡樹高。
AVL Tree
相較於BST，AVL 大幅地降低了不平衡的問題，但索引數量龐大的時候，會造成樹很高(degree很大)，若要查找的資料剛好落在葉子節點，則O(h)也是不小的開銷，因此樹高也是索引結構中，影響很大的一個要素。
B Tree
相對於BST，B Tree則是能夠將樹的高度維持，搜尋的時間複雜度為O(h) or O(logN)
B+ Tree
B+ Tree的特性，也能使搜尋的時間複雜度為O(h) or O(logN)，但可以發現，B+ Tree的葉子，才是實際上資料存放的位子，和B Tree有很明顯的不同
根據上述的視覺化後，可以做一個小結
B+Tree 資料結構優點
- 層級更少: 因為B+Tree的搜尋時間和樹高(層級)相關，層級少的情況下，搜索速度是快的
- 查詢速度更穩定: 由於B+Tree都 將資料儲存在葉子節點上，所以相較於B Tree(資料儲存在Node上)，搜尋速度是更加穩定的(每次都會走到葉子) - 天然排序:每個節點都可以使用Binary Search
- 節點儲存資訊少: 由於B+ Tree將資訊儲存在葉子節點，這樣每個節點可以存放更多的索引，使得一次性放入記憶體中運算的節點數量增加
- 葉子節點上的data都用 指針相連，可以提高區間訪問的性能
進階
在生產環境中的MySQL，會將非葉子節點(只存放冗餘索引和下個節點的地址)放在記憶體裡，所以在索引正常運作的情況下，會先在記憶體中運算，只有到最後的葉子節點，才會使用到I/O，能夠這樣運作，也是因為B+Tree只將資料儲存在葉子節點，而每個節點都有儲存資料的B Tree就不適合這樣的操作了。
透過記憶體和I/O的搭配操作，可以在資料量龐大的情況下，大幅提升搜尋速度。
How to work?
為甚麼說使用索引會加速搜尋速度呢?原理就是，原本存在資料庫的資料，若是無序的，搜尋上就會使用Linear Search，甚至可能會搜尋到整個表格空間，時間複雜度約為O(N)。
但若建立了索引，則可以利用B+ Tree的特性，讓搜尋的時間，降至O(logN)
When to use?
既然索引這麼厲害，那為甚麼不把所有的欄位都建立索引呢?原因主要有幾個..
-
建立索引需要額外的儲存空間
-
一開始有提到，索引是額外建立的一個資料結構，因此也需要儲存空間去存放，所以使用過多的索引，是會浪費儲存空間的。
-
索引的使用目的是快速搜尋
-
索引的確能夠加速資料的搜尋速度，方便進行搜尋，但也帶來了需要額外建置索引這個成本，因此如果資料的使用方式寫遠大於讀的話，使用索引反而是一件浪費資源的行為
索引失效
- != 或者 <>都會導致索引失效，變成全表掃描
- 類型不一致也會導致索引失效!比如col是varchar，但在查詢的時候不小心使用了int，雖然查詢結果會成功，但由於中間做了 隱式的類型轉換，會導致索引失效 - 對索引欄位使用count、sum等 函式操作，皆會造成索引失效 - 使用模糊搜尋時，如果字串前綴也是模糊搜尋，則索引會失效
- 在聯合索引下，查詢條件不滿足最左匹配原則(聯合索引的最左索引)，則會造成索引失效
- 在聯合索引的情況下，盡量使用明確的查詢代替 *，這樣就有機會走到覆蓋索引的機制，讓查詢速度加快
以上就是簡單的對於資料庫的索引簡單說明，以及使用的時機跟一些利弊，希望有讀到這篇的你，下次再遇到索引相關的問題，可以回答得更完整，希望對你有所幫助。
若是發現我理解錯誤，誤人子弟的，也可以隨時指教，我會非常感激!
心情
其實面試到這裡，蠻感謝自己那麼勇敢的，因為面試第一間Backend Engineer職缺的時候，是有被打擊到的，發現自己相當的不足，但好險自己的學習動機和那種渴望成長的決心蓋過了恐懼，才讓我敢於繼續面試Backend Engineer這個職位，也覺得在準備這些面試的過程中，很明顯的感受到自己的成長，不論所有的結果如何，都相當感謝面試官願意花這些時間和精力來用心的面試，希望自己之後也能成為這麼優秀的人。
最後想要分享朋友寫的一篇短文，讓我感觸很深
霍金的時間解釋裡面提到
兩朵星雲即使不動
也會因為宇宙的膨脹
而越來越遠
換言之，兩個人，只要靜止不動，就在分離。
雖然這篇是在講人的關係，但也讓我馬上體悟到，自己和目標，也是如此，只要停滯不前，就會越來越遠。
期許自己，不論在人生的哪個階段，都能夠持續的學習、不放棄挑戰，成為更好的自己(2022/08/26, Wen)