数据库课索引部分的学习笔记。
教材：
- Database System: The Complete Book, Chapter 15
- Database System Implementation, Chapter 3
为了便于解释原理，定义student类型：
typedef struct student {
unsigned int id;
string name;
double height;
} student;
1. 传统索引
传统索引结构中存放“键值-位置”对。假设有一堆student类型的数据，对id建立索引，那索引里每项是id值和指针构成的对：
typedef pair<unsigned int, student *> id_index_item;
typedef vector<index_item> id_index;
实际上student数据文件和索引可以不在内存里，但原理相同。比如文件student.txt里放了很多student值的记录，对它建立的索引里每项就是id值和指向文件里对应记录位置的指针。
1.1 基本概念
传统索引中的几个概念：
- Primary & Secondary
1- Primary Index = 主索引，建立索引的域决定文件顺序；
2- Secondary Index = 辅助索引，主索引之外都是辅助索引。
继续前面的例子，如果student.txt里的记录按id排序，那么对id建立的索引id_index就是主索引，对name建立的索引name_index就是辅助索引。
主索引中项和文件中记录顺序相同，主索引里第k项对应文件里第k条记录；辅助索引没有这种性质（对id排序的student记录，看name域的话可能就是乱序的）。
- Dense & Sparse
1- Dense Index = 稠密索引，每条记录都有索引；
2- Sparse Index = 系数索引，仅部分记录有索引。
文件存储和读写磁盘都以块为单位，假设一个块里能放16个student数据，对主索引来说文件里记录是有序的，所以主索引定义可以改为：
typedef pair<unsigned int, block *> id_index_item;
typedef vector<index_item> id_index
索引项的键是每个数据块第一个student的id。原本有N条student记录，稠密索引需要N项，稀疏索引只需要N/16项，存储索引需要的体积减少；对任意给定id，由于有序仍然可以通过稀疏索引定位到记录所在数据块，进而找到记录。
稀疏索引示意图
对辅助索引来说稀疏索引是没有意义的——索引中没出现的记录是找不到的。
- Multiple Level
可以对索引建立索引。
对于辅助索引，可以先建立第一层稠密索引，在稠密索引之上就可以建立稀疏索引，不过更常用的是后面的桶方法。
1.2 桶
桶（bucket）相当于一层稠密索引，但桶中的每项只含位置指针：
typedef student * bucket_item;
bucket示意图
二层稀疏索引+桶的查询方法和二层稀疏索引+一层稠密索引完全相同，但是桶中的项不含键值，所以一个数据块里能塞更多项，从而少了磁盘I/O次数。
桶的另一个优点是可以把多条件查询转为指针的集合运算。举书上的例子，要查满足studio = Disney而且year = 1995的记录。可以直接一条条记录找过去的话；可以先用studio索引找到studio为Disney的记录，检查它们的year是否为1995；或者可以如下图所示，分别用studio和year索引从各自的bucket里找到满足单个条件的指针集合，取交集后找真正的记录。三种方法哪种最好？
通过bucket查询
第三种。还是之前的道理，因为体积满足：
sizeof(bucket_item) < sizeof(index_item) < sizeof(student)
所以一个数据块里能塞的bucket_item最多，能塞的student最少。先通过bucket精确定位在读取，减少了要读的数据块数目。
1.3 Bitmap压缩
稍微扯点别的。通过bucket可以把多条件检索转化为指针集合取交集，那把指针进一步压缩就可以用bitmap。假设有n个记录，属性有m种取值，那么正常bitmap需要(m * n)比特，通过游程编码可以大致压缩到2nlog(m)个比特。
2. B-tree索引
传统索引的主要缺点是不灵活，所以商业系统里索引通常使用B树系列，这里只介绍B+ tree。
2.1 B+ tree结构
B+ tree取参数n，一个节点里可以容纳n个键值和(n + 1)个子节点指针，即：
typedef struct bptreenode {
unsigned int key[n];
bptreenode *children[n + 1];
} bptreenode;
n确定了键值和指针的数量上限，同时规定了一个节点指向子节点（叶子的子节点就是记录）的指针的数量下限：
B+ tree节点指向子节点的指针下限
对于叶节点，children[i]指向键值为key[i]的节点，多出来的children[n]指向下一个叶节点，这样在叶节点这一层上就形成了有序链表，便于做范围查询。比如取n = 3，每个节点可以放3个键值和4个指针，那么至少要有2个指针被用来指向记录，这样叶子节点至少有2个键值。
B+ tree叶节点
对于中层节点，children[i]指向子节点，想象key[-1]为负无穷，key[n]为正无穷，那么子树里所有记录都满足键值大于等于key[i-1]而小于key[i]——key划分区间，children指向区间。同样取n = 3，这是还是要用2个指针，但只需要1个键值被使用即可。
B+ tree中层节点
根节点就是特殊的中层节点，因为要兼容记录少（比如只有一条）的情况，所以放宽了限制。无论n取值为何，只要求至少2个指针被使用。
回头看那张表格，之所以中间节点是floor，叶节点是ceil，其实就是要求使用的指针不少于一半，而叶节点总有一个指向之后叶节点的指针。
2.2 B+ tree插入
如果插入的叶节点里记录数小于n，直接插入即可。这里只考虑怎样在溢出的情况下修复B+ tree的性质。概括地讲就是两步递归：分裂节点，向上传递。比如原本一棵B+ tree为：
原本的B+ tree
向其插入40，那么31/37/41那个叶节点分裂，按照顺序各保留一半的元素：
叶节点分裂
此时上层就需要插入键40，才能找到40/41那个叶节点。23/31/43这个中间节点插入40后也需要分裂，但这是就不是随意地一劈两半了：
分裂中间节点
中间节点需要分裂，那就表明含有(n + 1)个键值和(n + 2)个指针，分裂后的左节点保留前floor(n / 2)个键值和前floor((n + 2) / 2)个指针，右节点保留后ceil(n / 2)个键值和ceil((n + 2) / 2)个指针，多出来的中间一个键值和指向右节点的指针组成key-child对，向更高层插入。
其实就是一个节点分裂为两个时会多出一个键值，在上层看来分裂后又多了一个节点需要键来标记，这里有个B+ tree的visualization，玩几次能清楚不少：
https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
不过它家的版本似乎是分裂时右边保留较多的一半。
2.3 B+ tree性能
通常n取得很大，三层B+ tree就可以满足需求，一个B+ tree节点占一个数据块的话，三次磁盘I/O就可以搞定，而且根节点通常放在内存中，这样只需要两次。
3. Hash索引
传统hash表是静态的——桶的数量设置好不再变，发生冲突时采用拉链或者重定向，当整个hash表太拥挤时弄一张桶更多的hash表，把原来表里的元素重新hash到新表里。动态的hash表可以根据表中元素数量，自行扩充桶的数目。
3.1 可扩展Hash表
假设每个桶里能放两条数据，那桶数组可以定义为：
typedef vector<pair<block *, unsigned int>> buckets;
桶数组里每项是一个pair，block *指向数据块，unsigned int表示这个块使用了hash函数产生的值中多少位标记。假设hash函数产生的值有n比特，暂时只使用最前面的1比特，那么0/1两种取值可以标记两个桶：
使用1比特的桶数组
试图插入1111时，第一位为1所以插入第二个数据块，但里面满了所以需要分裂成两个数据块，先直接来看示意图：
插入1111引起分裂
1001/1100那个块插入1010根据hash值前两位分配到两个数据块里，桶数组里10和11分别指向两个数据块，而00和01指向同一个数据块。
这就是可扩展hash表的策略，把区分过程延后——如果目前数据块里能容纳所有记录，比如原来第二个块里的1001和1100，它们第一位比特相同，考虑第二位比特可分，但它们能放在一个数据块里就不做区分，而数据块溢出时，多考虑一位比特将超标的数据块分裂。
通常据块分裂时只需要改变指针，比如连续插入0010和0100会导致第一个数据块分裂，这时就让桶数组00和01就分别指向两个数据块；但区分数据需要的比特数超过标记桶号需要的比特数，比如插入1011刀1001/1010那个块后区分需要3比特，这时就要把桶数组大小翻倍（数据块只增加了一个）。
3.2 线性Hash表
可扩展hash表最大的缺点是桶数组尺寸增长太快，线性hash表的特点是每次桶数组只加一项。与可扩展hash表分裂冲突的数据块不同，线性hash表监控整张表的拥挤程度（元素数/桶数），拥挤程度超过阈值时在最后添加一个桶。因为不是特定让发生溢出的数据块分裂，所以需要拉链法处理冲突。
线性hash表示意图
其实线性hash和可扩展hash思路一脉相承，不知道为什么书上对线性hash就是从后取比特。0000和1010最后一位都为0，所以在同一个块里。
上图中i表示使用hash值中多少位，n表示桶的数量，r表示记录的数量。假设拥挤阈值为1.7，那么试图插图1010会导致过度拥挤，此时添加一个桶，多使用hash值中的1位：
插入1010
那么问题就来了，假设hash值取标记位后的值为m，怎么找到对应数据块呢？答案是分类，m小于n时就是第m个块，否则是第（m - pow(2, i - 1)）块。比如找11的话，就是3 - 2 = 1，找01那个桶。
这时插入0001，定位到0101/1111那个数据块，块满了但整体拥挤程度不超过阈值，所以拉链：
插入0001
3.3 Hash vs Index
严格来说hash也是一种index，所以这里index指的是B tree之类的有序索引，区别挺简单的，hash适合做具体值检索，index适合做范围检索。
网友评论