摘要
面試時,交流有關mysql索引問題時,發現有些人能夠濤濤不絕的說出B+樹和B樹,平衡二叉樹的區別,卻說不出B+樹和hash索引的區別。這種一看就知道是死記硬背,沒有理解索引的本質。本文旨在剖析這背後的原理,歡迎留言探討
問題
如果對以下問題感到困惑或一知半解,請繼續看下去,相信本文一定會對你有幫助
- mysql 索引如何實現
- mysql 索引結構B+樹與hash有何區別。分別適用於什麼場景
- 資料庫的索引還能有其他實現嗎
- redis跳錶是如何實現的
- 跳錶和B+樹,LSM樹有和區別呢
解析
首先為什麼要把mysql索引和redis跳錶放在一起討論呢,因為他們解決的都是同一種問題,用於解決數據集合的查找問題,即根據指定的key,快速查到它所在的位置(或者對應的value)
當你站在這個角度去思考問題時,還會不知道B+樹索引和hash索引的區別嗎
數據集合的查找問題
現在我們將問題領域邊界劃分清楚了,就是為了解決數據集合的查找問題。這一塊需要考慮哪些問題呢 1. 需要支持哪些查找方式,單key/多key/範圍查找, 2. 插入/刪除效率 3. 查找效率(即時間複雜度) 4. 存儲大小(空間複雜度)
我們看下幾種常用的查找結構
hash