分享一个小故事: 依稀记得人生第一次面试终面的时候, 那家公司的CTO问我数据库中有哪些索引. 正好读书时学过一门课叫做DBMS Implementation, 于是就巴拉巴拉列了一堆. 瞬间面试官就两眼发光的看着我, 说我既然知道bitmap, 一定是个上课认真学习的好孩子, 就兴高采烈的给我发了offer.

所以说年轻人, 认真读了这篇博客之后, 你就可以顺利的拿到offer, 从此走上成为CTO赢取白富美的康庄大道!

p.s. 写的稍微有些粗糙, 有不明白的可以直接给我留言或发邮件, 笔芯.

一个属性的查询

通俗的说, 就是select语句后边, 只对一个属性进行过滤, 例如:

1
2
3

select * from Employees where id = 15567;
select * from Employees where age = 25;
select * from Employees where age>20 and age<50;

常用的算法如下:

线性扫描

因为如果b条记录是无序的, 只能通过线性扫描进行查找.
时间复杂度: 最好 O(1), 平均 b/2, 最差 b

题外话+1: 对于乱序存储, 每条记录(tuple)直接存在一个文件(heap file)中. 删除记录: 标记删除而不是物理删除. 添加记录: 在文件的最末端插入一条记录.

二分查找

如果记录是有序存储的话, 自然想到可以用二分查找.

这么做查询虽然起飞了, 但插入数据的效率降低了(每插入一个数据都要重新更新保存所有数据. 这个世界就是这样, 无论什么都是有trade off的).

所以对数据库的有序存储做了一个优化: 首先按范围分好区间, 每一块代表一个page(见下图), 当某个区间存满了之后, 会链接(link)一个新的Overflow Page继续存储. 因为大部分情况下, 都是少量的插入与删除(Large-scale file re-arrangement occurs less frequently). 最终可以二分查找搜索page, 再去遍历搜索具体的记录.