多於1列的B樹索引是什麼樣的？

所以我讀了有關索引和實施，我偶然發現了這個網站，有B樹索引的簡要說明：多於1列的B樹索引是什麼樣的？

http://20bits.com/articles/interview-questions-database-indexes/

B樹索引非常有意義將對索引只在一個列上，但是假設我創建了一個包含多列的索引，那麼b-tree如何工作？ b-tree中每個節點的價值是什麼？

舉例來說，如果我有這樣的表：

table customer: 
id number 
name varchar 
phone_number varchar 
city varchar

，我創建一個索引：（ID，姓名，市）

，然後運行下面的查詢：

SELECT id, name 
    FROM customer 
WHERE city = 'My City';

，這如何查詢使用多列索引，或者它不使用它，除非指數爲（市，編號，名稱）或（市，姓名，身份證），而不是創造出來的？

來源

2009-10-30 Lawrence

想象一下，關鍵是由一個Python元組（col1，col2，col3）表示...索引操作涉及比較tuple_a和tuple_b ...如果您不知道col1和col2的哪個值有興趣，但只有col3，那麼它將不得不讀取整個索引（「全索引掃描」），這不是很有效。如果你有一個關於（col1，col2，col3）的索引，那麼當WHERE子句包含對（1）所有3列（2）的引用時，任何RDBMS都將使用該索引（以直接方式））col1和col2（3）只有col1。

否則（例如，僅在WHERE子句中COL3），無論是RDBMS將不使用索引在所有（例如SQLite的），或將做一個完整的索引掃描（例如Oracle）的[如果沒有其他索引是更好。

在您的具體示例中，假設id是客戶的唯一標識符，將其顯示在索引中是沒有意義的（除了您的DBMS應爲主鍵或列標記爲UNIQUE ）。

來源

2009-10-30 07:06:23

對於Oracle不適用。索引完整掃描，跳過掃描或快速完整索引掃描不需要使用前導列。 – 2009-10-30 08:35:04

@David：謝謝。我已經編輯了我的答案，以便人們不需要延遲對第一句話的判斷，直到有人閱讀了更多的細則;-) – 2009-10-30 10:11:03

對於大多數實現中，密鑰是簡單地較長的鍵，包括所有的鍵值，具有隔板。沒有魔法有;-)

在您的例子中的鍵值可能看起來像

 
"123499|John Doe|Conway, NH" 
"32144|Bill Gates| Seattle, WA"

其中的一個指標複合主鍵的特點是，中間樹節點能夠在某些情況下可以用於「覆蓋」查詢。

例如，如果查詢是要找到名稱和城市給出的ID，因爲ID是第一個在指數，該指數可以通過這個有效地搜索。一旦進入中間節點，它就可以從密鑰中「解析」名稱和城市，並且不需要去葉節點讀取它們。

然而，如果想查詢也顯示電話號碼，那麼邏輯將在完整記錄發現隨之回落葉子。

來源

2009-10-30 06:03:50 mjv

這是一個很好的第一直覺，但實現可能更多，例如，數據的類型（數字，可變長度文本和Postgres中常見的異常文本），所以任何級聯都需要在零碎上使用，需要一些數據字典。僅索引掃描也需要工作。此外，Oracle索引組織的表格是存儲整個表格的B樹（B * - 樹），包括非索引列。在所有這些情況下，必須將列數據分隔以恢復信息。可能的例外情況：對CHAR進行常規索引掃描 – 2018-01-08 09:03:31

一些實施方式簡單地級聯中的值的列的順序，與分隔符。

另一個解決方案是簡單地具有B-樹中的B-樹。當您在第一列上點擊一片葉子時，您會得到匹配記錄列表和下一列的小型B樹，等等。因此，索引中指定的列的順序對於該索引對於特定查詢是否有用產生巨大影響。

這裏有一個相關的問題，我上週寫道：

Does SQL Server jump leaves when using a composite clustered index?

來源

2009-10-30 06:20:19 richardtallent

除了已經描述過的「複合鍵」的機制，一種可能性是kdtree它就像一個二叉樹，但你遍歷每個您通過k維度循環。也就是說，樹的第一層將第一維分爲兩部分，第二層分割第二維，第二層再次分割第一維，等等。這允許在任意數量的維度中有效地劃分數據。這種方法在「空間」數據庫（例如Oracle Spatial，PostGIS等）中很常見，但在「常規」多索引表中可能不太有用。

http://en.wikipedia.org/wiki/Kd-tree

來源

2009-10-30 06:43:22

它可以使用（ID，姓名，市）指數，以滿足「城市=？」謂詞，但非常非常inefficently。

爲了使用索引來滿足這個查詢，它需要遍歷大部分樹結構來查找所需城市的條目。這仍然可能比掃描桌子的速度更快！

（city，name，id）的索引將是您查詢的最佳索引。它可以輕鬆找到所有想要的城市條目，並且不需要訪問基礎表以獲取id和名稱值。

來源

2009-10-30 06:50:27

在Oracle中，即使不過濾前導列，也可以使用組合鍵索引。這是通過三種機制完成的：

快速全索引掃描，其中多塊讀取用於遍歷整個索引段。
一個索引全掃描，其中索引是按塊的邏輯順序讀取的（我相信我已經讀過，在最近的版本中Oracle可以使用多塊讀取功能，但實際上您應該依靠單塊讀取）
一個inddex跳過掃描，其中非謂詞前導列的基數非常低，允許Oracle執行多個索引範圍掃描，每個前導列的唯一值一個索引範圍掃描。這些在我的經驗中非常罕見。

查找Richard Foote或Jonathan Lewis的文章以獲取有關Oracle索引內部的更多信息。

來源

2009-10-30 08:42:09

多於1列的B樹索引是什麼樣的？

回答

相關問題