行式存储的问题
读某个列必须读入整行 行不等长，修改数据可能导致行迁移 行数据较多时可能导致行链
黄志洪 2011.3.25 Copyright © 2010 Sequel Corporation
行式存储的访问路径
全表扫描 行标识访问
黄志洪 2011.3.25 Copyright © 2010 Sequel Corporation
列式数据库存储原理
黄志洪 2011.3.25 Copyright © 2010 Sequel Corporation
传统数据库的行式存储
数据存放在数据文件内 数据文件的基本组成单位：块/页 块内结构：块头、数据区
黄志洪 2011.3.25 Copyright © 2010 Sequel Corporation
LF索引：改进的位图索引
无须行号——行标识对应 只面向低坐标值的情况，无须使用B树辅助检索关键值 位向量压缩策略：0或1占比例<20%或>80%，压缩，否则不压缩 位图索引和查找表可以做成同一个结构
黄志洪 2011.3.25 Copyright © 2010 Sequel Corporation
HG索引：改进的B树索引源自黄志洪 2011.3.25 Copyright © 2010 Sequel Corporation
列式 vs 行式 行式
数据与索引分离
列式
数据与索引一体
数据几乎不压缩
数据压缩
操作某列必须读出整行
能直接读取某列数据
黄志洪 2011.3.25 Copyright © 2010 Sequel Corporation
黄志洪 2011.3.25 Copyright © 2010 Sequel Corporation
B树索引的弱点
空间代价，创建时间代价，维护代价 重复值多时影响效率
黄志洪 2011.3.25 Copyright © 2010 Sequel Corporation
位图索引
原理
黄志洪 2011.3.25 Copyright © 2010 Sequel Corporation
行标识访问：B树索引
黄志洪 2011.3.25 Copyright © 2010 Sequel Corporation
B树索引原理：结点
黄志洪 2011.3.25 Copyright © 2010 Sequel Corporation
B树索引原理：树形
利用B树进行查询——access path B树插入——分裂结点 B树删除——合并结点
列式数据库基本存储：FP索引
黄志洪 2011.3.25 Copyright © 2010 Sequel Corporation
FP索引 ：细节
FP1，FP2，FP3，flat FP 存储替换值得好处：压缩、等宽 怎样通过行号定位该行数据的相应位置
黄志洪 2011.3.25 Copyright © 2010 Sequel Corporation
HG索引：改进与优点
结合B树与位图的优点 天生适合Group by、select distinct等聚合操作 结构可以附加在查找表上，增加B树和指向G-Array的指针
黄志洪 2011.3.25 Copyright © 2010 Sequel Corporation
HNG索引：bitwise index
FAQ时间
Copyright © 2010 Sequel Corporation
21
位向量压缩：分段长度编码
i，j的意义及压缩算法
黄志洪 2011.3.25 Copyright © 2010 Sequel Corporation
位向量维护
删除：位向量相应位置改0，行号-行标识表打上删除标记 插入：只需修改跟key值有关的位向量，原因是压缩算法忽略位向量最后连续的0，在 行号-行标识里记录新行 修改：只需修改有关的2行
数据以位方式存储，按位垂直切片 相当一部分列满足稀疏条件，可以压缩
黄志洪 2011.3.25 Copyright © 2010 Sequel Corporation
Bitwise：计算
压缩减少IO，可并行计算 适合计算总和、平均值等汇总数据，不适合分组聚合
黄志洪 2011.3.25 Copyright © 2010 Sequel Corporation
黄志洪 2011.3.25 Copyright © 2010 Sequel Corporation
HG索引：G-Array
存储行号，等宽线性存储，64K页可以存储4K个行号 如果行号存满一个page，自动转换为位图形式存储 如果建立在主键或唯一约束列上，则不存在G-Array
黄志洪 2011.3.25 Copyright © 2010 Sequel Corporation