我想了解更好的索引組織。 假設我們有一個表2列:如何組織多列B樹索引
CREATE TABLE user(
name varchar(100)
,age int)
我們想創建一個索引:
CREATE INDEX IDX_MultiColIdx on user(name,age)
如何將B樹索引的組織是什麼樣子?
如果有一列,如年齡,組織是明確的:每個非葉子節點將包含一組將被用於搜索的整數鍵。哪些值包含我們的IDX_MultiColIdx B樹索引的節點?
我想了解更好的索引組織。 假設我們有一個表2列:如何組織多列B樹索引
CREATE TABLE user(
name varchar(100)
,age int)
我們想創建一個索引:
CREATE INDEX IDX_MultiColIdx on user(name,age)
如何將B樹索引的組織是什麼樣子?
如果有一列,如年齡,組織是明確的:每個非葉子節點將包含一組將被用於搜索的整數鍵。哪些值包含我們的IDX_MultiColIdx B樹索引的節點?
哪個值包含了我們IDX_MultiColIdx B樹索引的節點?
name
的,age
值和行指針(RID
/ROWID
或聚集鍵,取決於表組織),字典順序排序。
它們的存儲方式取決於數據類型和數據庫系統。
通常情況下,CHAR
用空格填充直到其大小,而VARCHAR
用其長度預置。
MyISAM
和一些其他的引擎可以使用鍵壓縮:一組鍵的匹配部分只存儲一次,而其他按鍵只保存不同的部分,像這樣:
Hamblin
Hamblin, California
Hamblin (surname)
Hambling Baronets
Hambly
Hambly Arena
Hambly Arena Fire
Hambo
Hambo Lama Itigelov
Hambok
Hambone
會存儲爲:
Hamblin
[7], California
[7] (surname)
[7]g Baronets
Hambly
[6] Arena
[6] Arena Fire
Hambo
[5] Lama Itigelov
[5]k
[5]ne
,其中[x]
指 「採取從以前的重點龍頭x
字符」
我假設你問的內部數據庫實現,因爲你提到'非葉節點'。
b樹中的內部節點不需要存儲完整的密鑰;他們只需要存儲分隔符。前綴和後綴壓縮意味着內部節點可以非常密集,因此可以減小b樹的高度,從而提高整體性能。
例如,給定索引與連續鍵<'非常長的字符串',314159>和<'不同一個字符串',9348>,所有內部節點需要表示的是這些鍵之間的分隔,可以用一個字符表示。以類似的方式,當要在內部節點中分離的鍵具有共同的前綴時,該前綴只需要被存儲一次,並且它們分開的點表示。
葉節點需要存儲完整的鍵值,並且可以存儲在用於鍵序遍歷的鏈表中。葉節點頁面可以通過使用前綴壓縮或其他技術進行壓縮以進一步減少樹高。
有關此方面的很好參考,請參閱Gray的「交易處理:概念和技術」& Reuter,如果需要更多詳細信息,請參閱參考資料。
插入或搜索鍵時,您將不得不忽略長度,因爲不等式如'... where colm>'xyz'將變得非常低效。 – paxdiablo 2010-09-15 07:19:53
@paxdiablo:「忽略長度」是什麼意思? – Quassnoi 2010-09-15 07:36:08
這是關於你的「而VARCHAR是以其長度作爲前綴」的評論。我的意思是,如果您使用「」作爲比較鍵,它將主要以「名稱長度」順序而不是「名稱」順序。換句話說,它將排序'a,b,c,aa,ff,bbbbb'而不是'a,aa,b,bbbbb,c,ff'。存儲長度的位置並不重要(只要您可以在密鑰中找到它),只是不要使用長度進行排序/比較。 –
paxdiablo
2010-09-15 07:44:16