再看索引

閑扯

很多年前我去面試的時候，人家問我，你說一個經典演算法，然後簡述一下。

我脫口而出：「二分查找算不算經典？」

人家說是，但是那天我並沒有答出來，因為時間長都沒有看了，當然最後我還是被那家單位錄取了。

二分查找就是這麼經典，雖然看起來很簡單，但是用處特別多。

二分查找在索引檢索的實踐

上次說過了，索引是有序的，比如說下面這個序列代表了索引：

[1,2,3,4,5,5,6,7,7,7,8,8,9,9,12,12,15,16]

現在有這麼一個SQL：

select a from tb1 where a=12;

a是索引列，值就是我上面寫的那個列表，這個SQL語句如果讓我寫演算法檢索我會選擇什麼演算法？我會繼續不假思索的喊出那四個字：二分查找！

只要我在這個索引列表中找到所有12這個元素的位置，我的SQL基本上就完成了，接下來我只要從索引結構的元組中找到對應的主鍵信息，然後做一個主鍵查詢就可以了。

下面我就寫一個二分查找的代碼：

def binary_search(l, key): low = 0 high = l[len(l) - 1] while high > low: mid = int(low + (high - low) / 2) if l[mid] > key: high = mid - 1 elif l[mid] < key: low = mid + 1 else: return midif __name__ == "__main__": l = [1, 2, 3, 4, 5, 5, 6, 7, 7, 7, 8, 8, 9, 9, 12, 12, 15, 16] pos = binary_search(l, 12) print(pos) print(l[pos])

這段代碼會找到第一個12並列印出來，至於這個列表中的其他12，這個演算法也可以進行改進，這些都可以在網上搜索到。

如果SQL改成a>=12或者a<12這樣，其實也是二分查找的變體，無非是要首先找到key，然後再做其他操作。

再說的深入一點點

剛才那個SQL：

select a from tb1 where a = 12;

其實上面的Python代碼里已經可以直接把結果返回了，不需要再去做什麼主鍵查詢了，因為需要的值索引里就有。這種情況在MySQL中叫做索引覆蓋，這是非常重要的也很有用的特性，用的好了，索引設計的又好，可以節省很多SQL執行成本。

另外，索引一般可以理解成按照元組形式存儲，元組的兩個元素分別是索引值和主鍵值，這樣在找到了索引以後可以根據主鍵來進行查找了。

閑扯

Life is short, you need Python!

這次的題圖是蟒蛇，因為這個世界需要Python！

推薦閱讀：