第一眼看到這個問題，皮皮也是很迷惑的，誰沒事會問這種問題。然而，事實上這居然是一道真實的面試題。
本來皮皮以為“皮友”只是皮著調侃一下的，既然是道面試題，那就要稍微地分析分析、說道說道了。
首先，從時間上來說，這是不同時期的兩個典型產品，MySQL要早於Kafka。
首先我們來說一說MySQL的歷史。MySQL可以追溯到1979年，一個名為Monty Widenius的程序員在為TcX的小公司打工，並且用BASIC設計了一個報表工具，使其可以在4MHz主頻和16KB內存的計算機上運行。當時，這只是一個很底層的且僅面向報表的存儲引擎，名叫Unireg。1990年，TcX公司的客戶中開始有人要求為他的API提供SQL支持。Monty直接藉助於mSQL的代碼，將它集成到自己的存儲引擎中。令人失望的是，效果並不太令人滿意，決心自己重寫一個SQL支持。
1996年，MySQL 1.0發佈，它只面向一小撥人，相當於內部發布。到了1996年10月，MySQL 3.11.1發佈(MySQL沒有2.x版本)，最開始只提供Solaris下的二進制版本。一個月後，Linux版本出現了。在接下來的兩年裡，MySQL被依次移植到各個平臺。2000年，MySQL不僅公佈自己的源代碼，並採用GPL(GNU General Public License)許可協議，正式進入開源世界。同年4月，MySQL對舊的存儲引擎ISAM進行了整理，將其命名為MyISAM。2003年12月，MySQL 5.0版本發佈，提供了視圖、存儲過程等功能。2010年12月，MySQL 5.5發佈，其主要新特性包括半同步的複製及對SIGNAL/RESIGNAL的異常處理功能的支持，最重要的是InnoDB存儲引擎終於變為當前MySQL的默認存儲引擎。
好了，再來簡單聊聊Kafka的歷史。Apache Kafka最初由LinkedIn開發，並在2011年初開源。在2012年10月23日由Apache Incubator孵化出站，成為了Apache軟件基金會的項目。2014年11月， Jun Rao、Jay Kreps、 Neha Narkhede等幾個曾在LinkedIn為Kafka工作的工程師，創建了名為Confluent的新公司，並著眼於Kafka。根據2014年Quora（美版知乎）的帖子，Jay Kreps將Kafka以作家Franz Kafka（奧匈帝國作家，代表作：《變形記》）命名。Kreps選擇將該系統以一個作家命名是因為，它是“a system optimized for writing”（一個用於優化寫作的系統），而且他很喜歡Kafka的作品。
從時間上來說，先者不能預測未來的事情，也就是說MySQL不能預測未來某個產品的架構以及其能夠從此未來架構上吸取點什麼經驗。但是前面的這些說辭只能用來做加分項，要徹底說服面試官顯然還是不行的。MySQL經歷了這麼多年的變遷和改進，底層的存儲引擎也有好多個，比如MyISAM、InnoDB，如果覺得某個東西適合自己，是可以在這個變遷的過程中引進過來。
技術面試，還是要從技術的角度去剖析。回答這個問題，除了要考慮時間這個加分項之外，還要說道以下3個技術點：1. MySQL中的索引機制；2. Kafka中的索引機制；3. MySQL與Kafka索引機制的對比。
何為索引？很多人都知道“索引是一個排序的列表，在這個列表中存儲著索引的值和包含這個值的數據所在行的物理地址，在數據十分龐大的時候，索引可以大大加快查詢的速度，這是因為使用索引後可以不用掃描全表來定位某行的數據，而是先通過索引表找到該行數據對應的物理地址然後訪問相應的數據。
索引的建立對於MySQL的高效運行是很重要的，索引可以大大提高MySQL的檢索速度。拿漢語字典的目錄頁（索引）打比方，我們可以按拼音、筆畫、偏旁部首等排序的目錄（索引）快速查找到需要的字。但過多的使用索引將會造成濫用。因此索引也會有它的缺點：雖然索引大大提高了查詢速度，同時卻會降低更新表的速度，如對錶進行INSERT、UPDATE和DELETE。因為更新表時，MySQL不僅要保存數據，還要保存一下索引文件。
索引是在MYSQL的存儲引擎層中實現的，而不是在服務層實現的。所以每種存儲引擎的索引都不一定完全相同，也不是所有的存儲引擎都支持所有的索引類型。MYSQL目前主要提供了以下4種索引 :
- B/B+樹索引：最常見的索引類型，大部分引擎都支持B樹索引。
- HASH 索引：只有Memory引擎支持，使用場景簡單。
- R-Tree 索引(空間數據索引)：空間索引是MyISAM的一種特殊索引類型，主要用於地理空間數據類型。
- Full-text (全文索引)：全文索引也是MyISAM的一種特殊索引類型，主要用於全文索引，InnoDB從MYSQL5.6版本提供對全文索引的支持。
其它索引類別：還有很多第三方的存儲引擎使用不同類型的數據結構來存儲索引。例如TokuDB使用分形樹索引（fractal tree index），這是一類較新開發的數據結構，既有B-Tree的很多優點，也避免了B-Tree的一些缺點。多數情況下，針對InnoDB的討論也都適用於TokuDB。ScaleDB使用Patricia tries，其他一些存儲引擎技術如InfiniDB和Infobright則使用了一些特殊的數據結構來優化某些特殊的查詢。
我們知道MySQL從5.5版本開始就將InnoDB作為了默認的存儲引擎，在《高性能MySQL》一書對於如何選擇存儲引擎就發表過這樣的觀點：除非需要用到某些InnoDB不具備的特性，並且沒有其它辦法可以替代，否則都應該優先選擇InnoDB引擎。雖然從學術陳詞上來說並不太嚴謹，但是我們可以簡單的認為：在絕大多數情況下，現在我們所說的MySQL所使用的引擎為InnoDB，而索引是在存儲引擎中實現的。“為什麼MySQL的索引不採用kafka的索引機制？”這個命題也可以簡單的修改為“為什麼InnoDB中不採用Kafka的索引機制？”
MySQL中的存儲引擎有很多，除了MyISAM、InnoDB之外，還有Archive、Blackhole、CSV、Federated、Memory、Merge、NDB、Groonga、OQGraph、Q4M、SphinxSE、Spider、VPForMySQL….等等，每個存儲引擎多針對的優化場景也不同，而且這裡我們無法針對每個存儲引擎來做分析，所以這裡我們針對最最通用的InnoDB來做進一步的分析。
為了弄清楚“為什麼mysql的索引不採用kafka的索引機制？”或者“為什麼InnoDB中不採用Kafka的索引機制？” ，那麼我們還是先來複習一下Kafka中的索引機制。
在kafka中，每個日誌分段文件都對應了兩個索引文件——偏移量索引文件和時間戳索引文件（還有其它的諸如事務日誌索引文件就不細表了），主要用來提高查找消息的效率。偏移量索引文件用來建立消息偏移量(offset)到物理地址之間的映射關係，方便快速定位消息所在的物理文件位置；時間戳索引文件則根據指定的時間戳(timestamp)來查找對應的偏移量信息。
Kafka 中的索引文件以稀疏索引(sparse index)的方式構造消息的索引，它並不保證每個消息在索引文件中都有對應的索引項。每當寫入一定量(由 broker 端參數 log.index.interval.bytes 指定，默認值為 4096，即 4KB)的消息時，偏移量索引文件和時間戳索引文件分別增加一個偏移量索引項和時間戳索引項，增大或減小 log.index.interval.bytes 的值，對應地可以縮小或增加索引項的密度。
稀疏索引通過 MappedByteBuffer 將索引文件映射到內存中，以加快索引的查詢速度。偏移量索引文件中的偏移量是單調遞增的，查詢指定偏移量時，使用二分查找法來快速定位偏移量的位置，如果指定的偏移量不在索引文件中，則會返回小於指定偏移量的最大偏移量。時間戳索引文件中的時間戳也保持嚴格的單調遞增，查詢指定時間戳時，也根據二分查找法來查找不大於該時間戳的最大偏移量，至於要找到對應的物理文件位置還需要根據偏移量索引文件來進行再次定位。稀疏索引的方式是在磁盤空間、內存空間、查找時間等多方面之間的一個折中。
以偏移量索引文件來做具體分析。偏移量索引項的格式如下圖所示。每個索引項佔用 8 個字節，分為兩個部分：(1) relativeOffset: 相對偏移量，表示消息相對於 baseOffset 的偏移量，佔用 4 個字節，當前索引文件的文件名即為 baseOffset 的值。(2) position: 物理地址，也就是消息在日誌分段文件中對應的物理位置，佔用 4 個字節。
消息的偏移量(offset)佔用 8 個字節，也可以稱為絕對偏移量。索引項中沒有直接使用絕對偏移量而改為只佔用 4 個字節的相對偏移量(relativeOffset = offset - baseOffset)，這樣可以減小索引文件佔用的空間。舉個例子，一個日誌分段的 baseOffset 為 32，那麼其文件名就是 00000000000000000032.log，offset 為 35 的消息在索引文件中的 relativeOffset 的值為 35-32=3。
如果我們要查找偏移量為 23 的消息，那麼應該怎麼做呢?首先通過二分法在偏移量索引文件中找到不大於 23 的最大索引項，即[22, 656]，然後從日誌分段文件中的物理位置 656 開始順序查找偏移量為 23 的消息。
以上是最簡單的一種情況。參考上圖，如果要查找偏移量為 268 的消息，那麼應該怎麼 辦呢?首先肯定是定位到baseOffset為251的日誌分段，然後計算相對偏移量relativeOffset = 268 - 251 = 17，之後再在對應的索引文件中找到不大於 17 的索引項，最後根據索引項中的 position 定位到具體的日誌分段文件位置開始查找目標消息。那麼又是如何查找 baseOffset 為 251 的日誌分段的呢?這裡並不是順序查找，而是用了跳躍表的結構。Kafka 的每個日誌對象中使用了 ConcurrentSkipListMap 來保存各個日誌分段，每個日誌分段的 baseOffset 作為 key，這樣可以根據指定偏移量來快速定位到消息所在的日誌分段。
在Kafka中要定位一條消息，那麼首先根據 offset 從 ConcurrentSkipListMap 中來查找到到對應（baseOffset）日誌分段的索引文件，然後讀取偏移量索引索引文件，之後使用二分法在偏移量索引文件中找到不大於 offset - baseOffset z的最大索引項，接著再讀取日誌分段文件並且從日誌分段文件中順序查找relativeOffset對應的消息。
Kafka中通過offset查詢消息內容的整個流程我們可以簡化成下圖：
我們再來複習MySQL（InnoDB）中的索引機制。可以說數據庫必須有索引，沒有索引則檢索過程變成了順序查找，O(n)的時間複雜度幾乎是不能忍受的。我們非常容易想象出一個只有單關鍵字組成的表如何使用B+樹進行索引，只要將關鍵字存儲到樹的節點即可。當數據庫一條記錄裡包含多個字段時，一棵B+樹就只能存儲主鍵，如果檢索的是非主鍵字段，則主鍵索引失去作用，又變成順序查找了。這時應該在第二個要檢索的列上建立第二套索引。 這個索引由獨立的B+樹來組織。有兩種常見的方法可以解決多個B+樹訪問同一套表數據的問題，一種叫做聚簇索引（clustered index ），一種叫做非聚簇索引（secondary index）。這兩個名字雖然都叫做索引，但這並不是一種單獨的索引類型，而是一種數據存儲方式。對於聚簇索引存儲來說，行數據和主鍵B+樹存儲在一起，輔助鍵B+樹只存儲輔助鍵和主鍵，主鍵和非主鍵B+樹幾乎是兩種類型的樹。對於非聚簇索引存儲來說，主鍵B+樹在葉子節點存儲指向真正數據行的指針，而非主鍵。
InnoDB使用的是聚簇索引，將主鍵組織到一棵B+樹中，而行數據就儲存在葉子節點上，若使用"where id = 14"這樣的條件查找主鍵，則按照B+樹的檢索算法即可查找到對應的葉節點，之後獲得行數據。若對Name列進行條件搜索，則需要兩個步驟：第一步在輔助索引B+樹中檢索Name，到達其葉子節點獲取對應的主鍵。第二步使用主鍵在主索引B+樹種再執行一次B+樹檢索操作，最終到達葉子節點即可獲取整行數據。
Kafka中消息的offset可以類比成InnoDB中的主鍵，前者是通過offset檢索出整條Record的數據，後者是通過主鍵檢索出整條Record的數據。InnoDB中通過主鍵查詢數據內容的整個流程建議簡化成下圖(下半部分)。
從上圖中我們也可以明顯的看到就檢索而言，InnoDB中的索引機制比Kafka中的索引機制要簡略一點，檢索效率應該也是InnoDB獲勝，我們將上圖中分為左中右三部分來分析：
- 最左部分：ConcurrentSkipListMap和B+樹索引的查詢時間複雜度都為logN，B+樹中的非葉子節點一般也可以都駐留在內存中，我們可以簡單的將Kafka中查找baseOffset對應的日誌分段和InnoDB中查找對應葉子節點的消耗看做差不多相等的，粗略算作平手。
- 最右部分：Kafka中後面通過索引讀取分段日誌文件的內容是一個頁的大小（可以思考下前面提及的“每當寫入一定量(由 broker 端參數 log.index.interval.bytes 指定，默認值為 4096，即 4KB)的消息時，偏移量索引文件和時間戳索引文件分別增加一個偏移量索引項和時間戳索引項”），B+樹中一個葉子節點也是一個頁的大小。最後都是從這塊內容中查找所要的內容，Kafka中是順序查找，InnoDB中還會有更有的方式去查找（比如以主鍵為搜索條件，可以使用Page Directory通過二分法快速定位），這裡比較而言，應該是InnoDB小勝。
- 中間部分：顯而易見，InnoDB獲勝。
Kafka中通過時間戳索引文件去檢索消息的方式可以類比於InnoDB中的輔助索引的檢索方式：前者是通過timestamp去找offset，後者是通過索引去找主鍵，後面兩者的過程就和上面的陳述相同。
我們再來思考一個問題：既然InnoDB的索引這麼厲害，那麼作為後起之秀的Kafka不採用呢？
我們還要考慮一個問題：InnoDB中維護索引的代價比Kafka中的要高。Kafka中當有新的索引文件建立的時候ConcurrentSkipListMap才會更新，而不是每次有數據寫入時就會更新，這塊的維護量基本可以忽略，B+樹中數據有插入、更新、刪除的時候都需要更新索引，還會引來“頁分裂”等相對耗時的操作。Kafka中的索引文件也是順序追加文件的操作，和B+樹比起來工作量要小很多。
說到底還是應用場景不同所決定的。MySQL中需要頻繁地執行CRUD的操作，CRUD是MySQL的主要工作內容，而為了支撐這個操作需要使用維護量大很多的B+樹去支撐。Kafka中的消息一般都是順序寫入磁盤，再到從磁盤順序讀出（不深入探討page cache等），他的主要工作內容就是：寫入+讀取，很少有檢索查詢的操作，換句話說，檢索查詢只是Kafka的一個輔助功能，不需要為了這個功能而去花費特別太的代價去維護一個高level的索引。前面也說過，Kafka中的這種方式是在磁盤空間、內存空間、查找時間等多方面之間的一個折中。
雖然寫了很多內容，但是肯定有很多疏漏的地方，如果你有其它的思考，歡迎在留言去留言探討。
閱讀更多 軟件真理與光 的文章
