為什麼 MySQL 資料庫要用 B＋樹存儲索引？
作者 | channingbreeze
責編 | 郭芮
小史是一個應屆生，雖然學的是電子專業，但是自己業餘時間看了很多互聯網與編程方面的書，一心想進BAT互聯網公司。
話說兩個多月前，小史通過了A廠的一面，兩個多月後的今天，小史終於等到了A廠的二面。
簡單的自我介紹後，面試官看了看小史的簡歷，開始發問了。
面試現場
小史：沒問題，這個項目前端用的react webpack，後端用的nginx SpringBoot Redis MySql，前後端分離的，最後用docker進行容器化部署。主要模塊有師生系統、課程系統、成績系統、選課系統等。
這個項目的架構和說辭，小史早已背得溜溜的。
小史：底層MySQL是存儲，Redis是緩存，DAO層操作MySQL，Cache層操作Redis，Service層處理業務邏輯，Rest API層為前端提供Rest介面。前端這邊用React進行模塊化，Webpack打包部署。網關Nginx進行負載均衡。MySQL、Redis、Nginx和SpringBoot應用都放在Docker里部署。
題目：為什麼MySQL資料庫要用B 樹存儲索引？
小史聽到這個題目，陷入了回憶。
前段時間的飯局
話說呂老師給小史講完人工智慧的一些知識後，他們一起回家吃小史姐姐做的飯去了。
【飯後】
呂老師：面試的時候一定是往深了問，不精通的話容易吃虧。不過面試時一般都是根據項目來問，項目中用到的技術，一定要多看看原理，特別是能和數據結構和演算法掛鉤的那部分。
小史：樹的話，無非就是前中後序遍歷、二叉樹、二叉搜索樹、平衡二叉樹，更高級一點的有紅黑樹、B樹、B 樹，還有之前你教我的字典樹。
【紅黑樹】
一聽到紅黑樹，小史頭都大了，開始抱怨了起來。
小史：紅黑樹看過很多遍了，但是每次都記不住，它的規則實在是太多了，光定義就有四五條規則，還有插入刪除的時候，需要調整樹，複雜得很。
呂老師：小史，問你紅黑樹，並不是讓你背誦它的定義，或者讓你手寫一個紅黑樹，而是想問問你它為什麼這樣設計，它的使用場景有哪些。
【B樹】
呂老師：小史，你要知道，文件系統和資料庫的索引都是存在硬碟上的，並且如果數據量大的話，不一定能一次性載入到內存中。
兩個月前，小史面試沒考慮內存情況差點掛了，傳送門......
【B 樹】
呂老師：這也是和業務場景相關的，你想想，資料庫中select數據，不一定只選一條，很多時候會選多條，比如按照ID排序後選10條。
小史：我明白了，如果是多條的話，B樹需要做局部的中序遍歷，可能要跨層訪問。而B 樹由於所有數據都在葉子結點，不用跨層，同時由於有鏈表結構，只需要找到首尾，通過鏈表就能把所有數據取出來了。
回到現場
小史：這和業務場景有關。如果只選一個數據，那確實是Hash更快。但是資料庫中經常會選擇多條，這時候由於B 樹索引有序，並且又有鏈表相連，它的查詢效率比Hash就快很多了。
小史：而且資料庫中的索引一般是在磁碟上，數據量大的情況可能無法一次裝入內存，B 樹的設計可以允許數據分批載入，同時樹的高度較低，提高查找效率。
HR和小史簡單地聊了聊基本情況，這次面試就結束了。
小史走後，面試官在系統中寫下了面試評語：
幾天後，小史收到了A廠的offer。
親愛的讀者們，面試現場的第一季到這裡就全部結束了，感謝大家的支持，我們一起期待小史後面的故事。
關於小史的面試故事，可點擊回顧呦：
作者：channingbreeze，國內某互聯網公司全棧開發。
聲明：本文為作者投稿，版權歸對方所有。
【完】
熱 文推 薦
TAG:CSDN |