Single-level ordered indexed

index

index是另外一個file，針對要被搜尋的欄位
减少block IO 的次数

顺序索引的类型

Primary index

本身档案是 sorted files
根据primary key排序
针对primary key建立索引档
记录每一个block的第一笔（Anchor Record）
有多少entry取决于有多少个block，然后index file有多少个block又取决于一个block能放多少个entry
有多少block取决于每笔记录的长度→每个block可以放几笔资料
查询
针对你要查询的值，先在index里面做binary search
插入和删除
问题：
解决：using an unordered overflow file
删除不直接删除，而使用deletion markers（lazy deletion）

Cluster index

本身是 sorted file
但按照nonkey排序，因此会有重复
索引比资料少（non dense）
对每一个不同的值有一个entry
记录第一个出现X的block
插入
可能会使index变动
解决办法：1、每个block多预留空间

Secondary index

现在档案按照别的栏位排序或者没有排序 （Non-ordering）
想要根据某一个栏位加速查询
每一个可能的值在index里都要出现
dense
如果indexing field是nonkey，而档案没有按照他的顺序排
建立两层index
第一层记录distinct value，第二层记录这个值出现的block

一个档案最多有一个primary index或者一个clustering index，不能兼而有之
一个档案可以有好几个secondary index
考虑index的代价，合理设置资料按什么排序

Dense & Nondense index

Multilevel indexes

• ISAM（Index Sequential Access Method）
  针对primary key可以有两层index

Dynamic multilevel indexes using B-trees and B+-trees

• B-Trees
  -- M-way search tree
  -- binary search tree 的延伸
  -- B-tree order
• B+-Trees
  --所有被搜寻的资料都是放在叶子节点
  --跟B-Tree不一样，B-tree资料本身也是标兵，B+树的非叶子节点只是帮助查询用的
  --好处是
  1、演算法比较简单
  2、Range query比较简单，因为都是在同一层里顺序存放的

Multiple dimensional Index

---

2016.6.14

---

Index on multiple keys

• multiple dimensional indexing
• applications
  -- multidimensional query(partial match range query)
  where (...) & (...)
  1 可以分别建立index 再把查询的结果做交集
  2 或者multilevel indexes
• partitioned hash
  hashing on (age, salary) 二维
  1 bit for age
  2 bit for salary
• grid files
  把多维空间切成格子
  lines取决于资料分布
  grid放在主记忆体
• kd-trees
• quad-trees
  每次都是切四份（四个象限）
  每个象限对应一个block
  如果哪一个block爆掉，就recursively切成四个象限
• R-trees
  n维的B+tree

Bitmap index

• 有多少笔记录就有多少个bit
• 根据想要查询的栏位建bitmap
• 做 logical and / or 运算
• 速度很快
• 适合cardinality低的 ，例如：性别，只有两种； 薪水，只有五个等级

SQL建index

Indexing of Strings

• Strings can be variable length
• 有时候会做 prefix compression

Tuning Indexes

• 什么时候要建立index：栏位经常被查询而速度较慢
• 也要看资料更新是不是很频繁，因为index会跟着动