Index索引
#

organizing
multiple keys
efficient

基本术语

Index file 存key/指针对
- 指针指向实际记录
- 可以线性地组织
- 可以非线性地组织
Primary key：对于记录的唯一标识
Secondary key：备用搜索key，一般不是唯一标识
- 常常作为搜索key

线性索引
#

简单的key/记录指针对‘s 序列

两级索引-多级索引

entry sequenced
变长记录彳亍
静态数据nice
频繁增删：贫弱

树索引
#

频繁增删
多个key结合
范围查找

2-3树
#

形态属性：

每个结点拥有一/两个【key/指针对】
每个内部结点要么有俩（1 key）要么有仨孩子（2 keys）
所有叶子在树中都在同一层，永远在高度上平衡

拥有和BST一样的搜索属性

插入原则
- 找到恰当的叶子L
- 如果L只有一个值
  - 插新key到L
- 否则
  - 把L分裂成2个结点 L和L’，L放这三个key中最小的，L’放最大的
  - 剩下的中间key被提拔到双亲结点，指向L'
    - 如果双亲结点只有一个key，那就直接跟在旁边
    - 否则（如果满），重复以上分裂-提拔过程
删除情况
- 删除有俩值的叶子结点的key
- 删除有一值的叶子结点的key
- 删除内部结点上的key

B树
#

B树是2-3的拓展ver

形状定义

m阶
- 根结点要么是叶子，要么至少有俩孩子（key/指针对）
- 对每个除了根以外的内部结点
  - 有[m/2] ~ m个孩子；向上取整⌈⌉
  - 有[m/2]-1 ~ m-1个 key/指针对
- 所有叶同层，高度平衡

B树具有BST属性

一个 B树结点大小（m-1）通常被定义得符合磁盘区块的大小

一个结点可以有数百个孩子

属性

平衡树
将key类同的记录放在同一个磁盘页，局部性原理
保障除根以外的结点处于几乎半满的状态
- 空间效率&减少磁盘访问量

结点中的关键字均由小到大排列

左小右大

B+树
#

B+树的内部结点 不存储 指针，只存储指导搜索的关键字 placeholders；
- 叶子存储keys/pointers到记录
叶子结点可能比内部结点存储的结点数 多些或少些

m阶B+树

根节点含有 1 ~ m-1 个关键字
除根以外的内部结点含有 [m/2]-1 ~ m-1 个关键字；
叶子结点含有 [n/2] ~n (n与 m可等可不等) 个关键字/记录指针对；
叶子结点彼此相链接构成一个有序链表，其头指针指向含最小关键字的结点

需要m和n来初始化

※ 在 B+ 树上，既可以进行缩小范围的查找，也可以进行顺序查找(在叶子结点层查找) ※ 在进行缩小范围的查找时，给定值<Ki，则应继续在 Ai-1 子树中进行查找，给定值>=Ki，则应继续在 Ai 子树中进行查找, 一直查到叶子结点 ※ 在进行缩小范围的查找时，不管成功与否，都必须查到叶子结点才能结束

B+ Tree Insertion

find the proper leaf node L
if L isn’t full, insert the new key into L else
1. split L into two (dividing the records evenly among the two nodes)
2. promote a copy of the least-valued key in the newly formed right leaf node to the parent
3. the promoted key is then inserted into the parent.
  
  a) if the parent contain isn’t full, then the promoted key and the newly right leaf node are simply added to the parent node,
  
  b) if the parent is full, then the split the parent into two nodes and promote the least-valued key in the right node to the parent.