定義

An index is a table/file of (keyVal 索引字段,tupleID 行指針) pairs
索引是定義在存儲表(Table)基礎(chǔ)之上，有助于無需檢查所有記錄而快速定
位所需記錄的一種輔助存儲結(jié)構(gòu)，由一系列存儲在磁盤上的索引項(xiàng)(index entries)組成，每一索引項(xiàng)又由兩部分構(gòu)成:

• 索引字段:由Table中某些列(通常是一列)中的值串接而成。索引中通 常存儲了索引字段的每一個(gè)值(也有不是這樣的)。索引字段類似于詞典中的詞條。
• 行指針:指向Table中包含索引字段值的記錄在磁盤上的存儲位置。行 指針類似于詞條在書籍、詞典中出現(xiàn)的頁碼。

image.png

類別

基于構(gòu)建索引的屬性 （是否為 unique）

• primary 主索引
  index on unique field, may be sorted on A（主碼）
  索引構(gòu)建在 unique 的 attribute上， 主文件在attribute 上有序存儲。
• clustering 聚簇索引
  index on non-unique field, file sorted on A（排序碼）
  索引構(gòu)建在 non-unique的 attribute上， 主文件在attribute 上有序存儲，行指針指向每個(gè)value 的第一次出現(xiàn)位置。
• secondary 多級索引/ 輔助索引
  輔助索引不能組織文件
  file not sorted on A

基于索引的結(jié)構(gòu) (索引 與 主文件的關(guān)系)

• dense 稠密索引
  every tuple is referenced by an entry in the index file
  索引項(xiàng) 與 主文件 記錄一一對應(yīng)
• sparse
  only some tuples are referenced by index file entries
  索引項(xiàng) 與 部分主文件 一一對應(yīng)
• single-level
  tuples are accessed directly from the index file
• multi-level
  may need to access several index pages to reach tuple

Primary index 主索引的 selection , insertion ,deletion

主索引 也是一種 dense 索引。
i : index pages

• 通過index找到 數(shù)據(jù)地址 + 讀 + 或讀溢出塊
  = log(i,2) + 1r + Ov

查詢速度塊，復(fù)雜度 O（log n）。

• 通過index找到 數(shù)據(jù)地址 + 更新索引 + 讀+ 或讀溢出塊 + 寫 + 或?qū)懸绯鰤K
  = log(i,2) + ( i / 2 ) * (1r + 1w) + (1 + Ov)r + (1+δ)w

*插入 需要重新組織文件， 復(fù)雜度O（n） *

：

• if we delete index entries by marking ...
  找到該數(shù)據(jù) + 寫disk + 更新索引O（1）
  = (log2 i + 1 + Ov)r + 2w

• If we delete index entry by index file reorganisation
  找到該數(shù)據(jù) + 更新索引O（n） + 寫disk
  = (log2 i + 1 + Ov)r + i/2.(1r+1w) + 1w

刪除 可以是O（log n ）， 也可以是O（n）,取決于是否重新組織文件

Clustering Index 聚簇索引

索引構(gòu)建在 non-unique 的屬性上，索引中臨近的記錄 在主文件中 也是臨近的。
一般是 稀疏索引。

cluster index

適用于：

1. range queries on A (find lower bound, then scan data)
2. pmr queries on A (search index for specified value）

插入： expensive ! 需要重新組織 index file and data file
刪除： 類似 primary index

Secondary index 輔助索引

輔助索引不能組織主文件數(shù)據(jù)， 所以主索引下面引入一個(gè)指針桶 secondary index file。
sparse index (Ix1) on dense index containing (key,offset) pairs
dense index (Ix2) containing just TupleId's

image.png

Insertion 插入:
每次插入， 索引 和 主文件都要同步更新，只 需要 重新組織索引文件
Deletion 刪除:
使用mark-style 的方式刪除記錄，周期性的 重新組織index 文件。

B-Trees

Multi-level Index 多級索引:當(dāng)索引項(xiàng)比較多時(shí)，可以對索引再建立索引，依此類推，形成 多級索引。
B樹索引： 一種以樹型數(shù)據(jù)結(jié)構(gòu)來組織索引項(xiàng)的多級索引.
B 樹最底層 （葉子節(jié)點(diǎn)）與 data file 是 一一對應(yīng)的 dense index .

depth=3, n=3

B樹 的插入

1. find leaf node and position in node where entry would be stored
2. if node is not full, insert entry into appropriate spot
3. if node is full, split node into two half-full nodes and promote middle element to parent
4. if parent full, split and promote

image.png

image.png

插入的復(fù)雜度
=

查找復(fù)雜度：
一次找到 data

search index to find leaf node for Lo
// 讀 每一個(gè) index ,在讀每個(gè)data 
for each leaf node entry until Hi found {
    access tuple t using TupleId from entry
}