InnoDB爲其索引實現B +樹時如何處理重複鍵。InnoDB B +樹索引 - 重複值

例如，如果有一百萬行有一個基數爲10的列的表。如果我們在此列上創建索引，結果B +樹將如何看起來像？

它只有10個密鑰，每個密鑰的值是屬於該密鑰的主密鑰列表（如果是，以什麼結構？鏈接列表？），還是會有1M個密鑰（如果是，則B +樹必須以不同的方式處理）？

2016-07-05 Vikk

從某種意義上說，InnoDB BTree沒有重複。這是因爲PRIMARY KEY的列被附加到爲輔助鍵指定的列。這導致完全有序的列表。

當您通過輔助鍵（或鍵的初始部分）查詢時，查詢將深入BTree以查找索引中與索引匹配的第一行，然後向前掃描以獲取其他索引。要獲得其餘列，需要PRIMARY KEY列進行第二次BTree查找。

優化器很少使用「低基數」的索引。例如，不應對索引是/否或真/假或男/女列進行索引。優化器可以更快地簡單地掃描表格，而不是在索引和（通過PK列）BTree主體之間來回跳動。

根據月亮的相位，什麼時候使用索引與浮動的截點在20％左右。

2016-07-09 17:53:39

謝謝瑞克。這似乎是有道理的。你有任何參考 - 在手冊或其他地方？ – Vikk

唉，沒有。文檔中有許多網頁，但它們往往更精確，不太實用。這是我收集的有關索引工作原理的一部分。我試圖將它改爲「可用」的方式。我反覆看到20％（10％到30％）的證明。 5.7重新設計了用於決定查詢計劃的「成本模型」，但仍然歸結爲我所說的。 –

不良指數

你提出的情況對B +樹來說是不好的。 10的基數意味着only 10 of the 1 million values are unique。實際上它不僅對B +樹不好，而且它通常是一個糟糕的指數。根據這個指數，你將平均剩下約一個子集。 100,000個值，您必須查看或使用其他值進一步過濾。

B +樹性質

關於結果樹的結構有一些事情要記住這裏：

插入可能需要拆分如果葉結滿

偶爾葉節點的分裂就必須下一個更高的節點

的分裂在最壞情況下的拆分可以層疊所有方式到根節點

https://www.percona.com/files/presentations/percona-live/london-2011/PLUK2011-b-

葉節點連接在一起作爲雙向鏈表

[...]

整棵樹可能不會在所有

https://www.percona.com/files/presentations/percona-live/london-2011/PLUK2011-b-

逛更高節點進行掃描

如果你插入了大量數據或多或少都屬於同一個等價類的鍵，我會期待一棵樹，這對你無用。這10個密鑰可能僅存在於根節點中，並且樹中所有深度較深的數據都將被排序（因爲沒有剩下的要排序）。

由於葉子是雙鏈表，所以基本上只剩下我在開頭所寫的內容：您必須遍歷值的大部分子集。關於給定的索引，這是必須要考慮的，B +樹在特定情況下可能會表現良好（列出所有數據都可以）。

實際上這更深入一個抽象：葉子是雙鏈接的，但每個葉子（數據或鏈接到PK）有多個值。儘管如此，這些也都在列表中，所以如果你只是遍歷所有東西，那麼它們就沒有什麼區別。

請看，你也可以調查什麼MySQL是真正的建築。有工具來檢查建索引數據結構，例如見

2016-07-05 07:48:07 GhostGambler

我知道這是一個不好的指數。這僅僅是爲了我對innodb內部的理解。對不起，你的回答並不清楚這些數據將如何存儲在樹中。我會嘗試鏈接中的工具。謝謝。 – Vikk

也許你應該只是閱讀我提供的兩個鏈接以及MySQL手冊。手冊中有（或者至少是）一章討論了MySQL內部，也許這對你來說也是有意義的（也許看一下老版本的手冊）。 – GhostGambler

的InnoDB存儲表中B +樹索引內部稱爲主。索引的關鍵是您的主要關鍵字段。

如果您定義了一個二級索引，則會有額外的B +樹索引（在.ibd或ibdata1中），其中鍵是次級索引字段，值是主鍵。

B +樹本身不需要密鑰是唯一的。 PRIMARY和所有UNIQUE索引的唯一性在服務器級別實施。

這裏有一些關於InnoDB如何組織索引並使用它們訪問數據的幻燈片。 http://www.slideshare.net/akuzminsky/efficient-indexes-in-mysql#downloads-panel

2016-07-05 14:38:49 akuzminsky