B+ 树、哈希与位图索引

正确答案：高选择性等值与范围查询并存 → B+ 树索引；主要为高选择性等值查询 → 哈希索引；低基数、读多写少且常组合筛选 → 位图索引；返回表中大部分记录 → 顺序扫描

索引选择要结合查询类型、选择性、数据规模、读写比和空间，而不是只看单次查找速度

正确答案：从根结点比较搜索键并选择子指针 → 在中间结点继续缩小键值范围 → 到达叶结点定位索引项 → 通过记录指针读取目标记录或判断不存在

平衡多级结构使所有叶结点深度相同，查找 I/O 随树高增长而不是随记录数线性增长

正确答案：叶结点按键有序相连，可以连续取得区间内后续键直到超过上界

叶链是 B+ 树同时支持点查和有序范围扫描的重要结构

正确答案：叶结点插入后溢出 → 分裂结点并把分隔键传播到父结点；删除后结点低于占用要求 → 向兄弟借键或合并并调整父结点；修改索引键 → 通常按旧键删除、按新键重新插入

分裂、借位和合并用于保持树平衡，但会增加写入和并发控制成本

正确答案：目标桶中直接找到键 → 返回对应记录指针；目标桶已满并发生冲突 → 继续检查溢出页或溢出链；检查目标桶及溢出链仍无键 → 判断该键不存在；数据规模长期增长 → 重组静态哈希或采用可动态扩展的哈希结构

哈希把键映射到桶，冲突和增长策略决定查找长度与维护成本

正确答案：每个低基数取值可以对应一个位向量、AND 可组合同时满足多个条件的记录、OR 可组合满足任一条件的记录、位计数可快速估计命中数量、频繁单行更新可能带来维护和并发成本

位图擅长低基数分析筛选，得到记录位置后仍可能需要回表读取其他列