# 1. 简介
索引类型：
- 前缀索引（Short Key Index）
- Ordinal 索引
- Zone Map 索引
- Bitmap 索引
- Bloom Filter 索引
Bitmap 和 Bloom Filter 不会默认生成，需要手段指定。
--------
# 2 文件格式
- Index Region: 每列的索引
## 2.1 Data Page
分为两类：nullable 和 non-nullable data pages。
**Nullable data page：**
```
+----------------+
| value count |
|----------------|
| first row id |
|----------------|
| bitmap length |
|----------------|
| null bitmap |
|----------------|
| data |
|----------------|
| checksum |
+----------------+
```
**Non-nullable data page:**
```
|----------------|
| value count |
|----------------|
| first row id |
|----------------|
| data |
|----------------|
| checksum |
+----------------+
```
- data：存储编码和压缩后的数据
--------------
# 3 前缀索引（Short Key Index）
## 3.1 索引组织
一种稀疏索引，每隔一定的数据行（默认1024）生成一条索引项。
前缀索引会对每一个索引间隔的第一个数据行的**前缀字段进行编码**，前缀字段的编码与前缀字段的值具有相同的排序规则。
前缀索引数据保存在一个独立的 **Short Key Page** 中。
- **Short Key Page:**
- 索引项目
- footer
- checksum
索引数据由两部分组成：
- 所有的 short keys 拼接（组成一个大buffer）
- 每个 short key 在 buffer 内的偏移（offset）
一个 short key 对应 1024 行
**Short Key Page footer:**
```protobuf
message ShortKeyFooterPB {
// How many index item in this index.
optional uint32 num_items = 1;
// The total bytes occupied by the index key
optional uint32 key_bytes = 2;
// The total bytes occupied by the key offsets
optional uint32 offset_bytes = 3;
// Segment id which this index is belong to
optional uint32 segment_id = 4;
// number rows in each block
optional uint32 num_rows_per_block = 5;
// How many rows in this segment
optional uint32 num_segment_rows = 6;
}
```
## 3.2 查询过滤
前缀索引是稀疏索引，不能精确定位到key所在的行，只能粗粒度地定位出key可能存在的范围，然后使用二分查找算法精确地定位key的位置，如下图所示。
---------
# 4 Ordinal 索引
## 4.1 索引结构
- 列级别的。
- 每个 data page 对应一个索引项，保存 Data Page 在文件内的 offset、page 大小和 page 的起始行号。
- 所有的索引都存储在一个 Index page 中， segment footer 中存储 index page 的指针。
- 如果该列只有 data page，那么就没有 index page， footer 中 mutable_root_page 直接指向那个 data page。
## 4.2 查询过滤
需要判断是否存在 index page 还是只有一个 data page。
-------
# 5 Zone Map 索引
- 列级别的：
包含了：
- 每个 Data Page 的 zone map
- segment 内该列的 zone map
每个 Data page 的 Zone map序列化后保存在 Index page 中。
Index page **可能会有多个**。
当有多个 Index page 时，每个 Index page 会生成一项 ordinal 索引项（保存在另外的 ordinal index page 中）。
------
# 6 Bitmap 索引
Bitmap 索引由两部分组成：
- 有序字典：有序保存（可以过滤大于、小于 field value 之类的）
- 字典值的 Roaring bitmap：posting list bitmap（行号）
数据为 `[x, x, y, y, y, z, y, x, z, x]`
Bitmap 存储了某个字典值出现在哪些行号里。
Bitmap 索引的字典数据和Roaring位图数据分开存储。
ordinal: 第几个词典值
-----
# 7 Bloom Filter 索引
每个 Data page 一个索引。
-------
# 参考资料
- [深度解析｜Apache Doris 索引机制解析](https://mp.weixin.qq.com/s?__biz=Mzg5MDEyODc1OA==&mid=2247498951&idx=4&sn=d61586bee5419d3cfe654fb1efc688ef&chksm=cfe3ecdef89465c894aee316c64200a3c0a498d483c748abdba326dc2453c63806509fbefb37&scene=178&cur_album_id=1507526553017090049#rd)