###### tags: `database` `note` `thu`
{%hackmd theme-dark %}

# Indexing Structures

## 種類
### Dense v.s. nondense index
- Dense: 每一個搜尋字串都能對到一個Index
- Nondense/sparse: 不一定都能對到

### 1. Primary Indexes (ordering field)
- 用來唯一定位到所需要的record的index。
- 一個檔案裡最多只有一個。
- nondense/sparse
e.g. 員工編號

### 2. Clustering index (ordering field)
- 用來定位到一群有相同ordering field的record。
- 跟Primary indexes無法共存在同一個檔案裡，一樣一個檔案裡最多只有一個。
- dense
e.g. 部門id

### 3. Secondary Indexes (nonordered field)
- 用來輔助Primary Indexes，提供另一種方式系統能索引到所需要的record。
- 通常為Secondary key，但也可以不是。
- nondense
e.g. 員工ssn

## 方法
### 1. Hash
### 2. B-Tree (下一頁[B-Tree](/wcCtFd90Q12UWzPnpC06SQ)會講)