發布日期：Dec 22, 2020
文章於 Jan 10, 2021 更新
為了讓找資料更快。但是這個「更快」是跟誰比較？是跟「沒有索引時從頭逐項查找」相比。
【情境模擬】 假設我們上網徵求「動畫推薦」，得到一些回應像這樣：
18:30 A網友「鋼鍊啦鋼鍊！」
18:45 B網友「有鋼鍊那也要推個銀之匙才行」
19:10 C網友「魔法阿嬤」
19:12 D網友「樂園追放，讚」
20:07 E網友「月刊少女野崎同學，會看到笑死」
21:17 F網友「夏目友人帳～」
所以我們得到了一份原始資料長這樣：
鋼之鍊金術師
銀之匙
魔法阿嬤
樂園追放
月刊少女野崎同學
夏目友人帳
當我們想要找這份動畫推薦清單裡有沒有某部動畫時，
最原始的做法就是從第一個檢查最後一個，這也是資料庫最原始的搜尋資料方式。
如果今天有人問我「樂園追放」這部動畫有沒有在清單裡？
我的印象是「我記得中間有人畫風一變，推了個『魔法阿嬤』，然後後面回答馬上又用『樂園追放』把畫風修回日本動畫了 XD」
這時候就有點帶進了「索引」觀念，因為這次我們不是一筆一筆檢查，而是直接由「魔法阿嬤」切入，找到緊接在後的「樂園追放」。
當清單內容變多時，「直接從某點切入搜索」的速度有很高的機率會比「逐項尋找」快速。
演算法裡的「二元搜尋樹」也是這樣的概念。找資料時從當下的切入點開始兵分兩路，直到找到目標。
「你要找的動畫是『魔法阿嬤』嗎？」 –> 不是
「資料在『魔法阿嬤』之前還是之後？」 –> 之後
「資料在『月刊少女野崎同學』之前還是之後？」 –> 之前
「你要找的動畫是『樂園追放』嗎？」 –> 是
更進一步，我們也可以將資料進行排序，例如將動畫按照出版年份或者作品名字的字數排序，試著加快搜尋的過程，
這就是不同索引方式的演進。
「索引」概念是強烈吃重演算法觀念的領域，「要如何安排資料才能找得更快、耗能更低」正是演算法大展長才之處。 根據索引背後使用的演算法不同，在不同資料情境下可能會產生搜尋速度的落差。
不同資料庫實現「索引」的方式也不盡相同，如果好奇的話需要研究該資料庫的底層設計。
舉例有個資料表長這樣，而我們用的資料庫是 MySQL(InnoDB): table_A
| column | is index ? |
|---|---|
| id | v |
| name |
SELECT * FROM table_A WHERE id = 3
會用 B+ 樹的概念搜尋SELECT * FROM table_A WHERE name = "Dingo"
跟沒設定索引一樣，只能逐筆找InnoDB: MySQL 資料庫可以採用的其中一種資料庫引擎，跟 InnoDB 相同作用的還有 MyISAM, MyRocks …… 等。更多資訊可參考 wiki - MySQL資料庫引擎的比較
在 InnoDB 中，它有提供的索引基本上分為兩大類 :
從進入的節點比大小，分兩路進下一層。下一層的節點會包含已排序的數個值，讓進入第三層的路線變成更多路，每層節點的可容納 key 數有上限，依照 tree 的設計而定(像是每個節點只能放 2~3 個 key 的設計會被稱為 2-3 tree)。
e.g. [find 13!] 7—- 12, 16– 18,23,25 | |- 13,14,15 | |- 8,9,11 | |– 2,5 —- 1 |- 3,4 |- 6