索引与B树结构学习笔记
一、索引的基本概念
1. 索引作为函数
2. 索引的核心思想
- 属性作为Key：将需要快速查询的属性作为索引键
- 排序存储：按键值排序，提高查找效率
- 指针映射：建立键值到数据位置的映射关系
二、B树索引详解
1. B树基本结构
2. B树特性与限制
阶数（Order）概念： - 阶n=3：每个节点最多容纳3个键值对 - 最小键数：⌈n/2⌉ - 1（除根节点外） - 平衡保证：所有叶子节点在同一层级
节点容量计算： - 最大键数：n-1 - 最小键数（非根节点）：⌈n/2⌉ - 1 - 子节点数：键数 + 1
3. B树操作机制
插入操作流程：
- 查找插入位置：从根节点开始，找到合适的叶子节点
- 直接插入：如果叶子节点有空间，直接插入
- 节点分裂：如果节点已满：
- 将当前节点分裂为两个节点
- 将中间键提升到父节点
- 在父节点中建立指向新节点的指针
- 根节点分裂：如果根节点需要分裂，创建新的根节点，树高度增加
插入示例（n=3）：
删除操作流程：
- 查找目标：定位包含要删除键的节点
- 叶子节点删除：
- 如果删除后仍满足最小键数要求，直接删除
- 否则需要合并或重新分配
- 内部节点删除：用前驱或后继键替换，递归处理
- 节点合并：当节点键数不足时，与兄弟节点合并
4. B树优势
- 平衡性：保证所有操作的时间复杂度为O(log n)
- 磁盘友好：每个节点对应一个磁盘页，减少I/O次数
- 范围查询：支持高效的范围扫描（叶子节点链表连接）
三、索引设计策略
1. 索引创建原则
适合创建索引的情况： - 高频查询属性：经常出现在WHERE条件中的字段 - 高区分度属性：唯一性高，如ID、邮箱等 - 稳定性好的属性：值不频繁变更，避免索引维护开销
不适合创建索引的情况： - 低区分度属性：如性别、状态标志等 - 频繁更新属性：索引维护成本高 - 大文本字段：索引体积过大，影响性能
2. 多值索引（复合索引）
// 创建复合索引示例
db.collection.createIndex({"lastName": 1, "firstName": 1})
// 有效查询：使用索引前缀
db.collection.find({"lastName": "Smith"})
db.collection.find({"lastName": "Smith", "firstName": "John"})
// 无效查询：跳过前缀
db.collection.find({"firstName": "John"}) // 无法使用该复合索引
复合索引设计原则： - 最左前缀匹配：查询必须使用索引的最左列 - 区分度排序：高区分度列放在前面 - 查询频率：高频查询条件优先
四、索引与存储结构的关系
1. 主索引（聚集索引）
- 基于主键：通常使用ID作为主索引键
- 数据物理排序：数据按主键顺序物理存储
- 替代inode：主索引可以替代传统的文件inode结构
2. 索引的存储优化
- 页对齐：索引节点大小与存储页对齐 - 指针优化：直接指针指向数据页，间接指针处理大文档 - 缓存友好：热索引节点常驻内存五、实践应用示例
MongoDB索引操作
// 创建单字段索引
db.users.createIndex({"email": 1})
// 创建复合索引
db.users.createIndex({"lastName": 1, "createdAt": -1})
// 查看索引
db.users.getIndexes()
// 索引性能分析
db.users.find({"email": "test@example.com"}).explain("executionStats")
索引选择策略
// 好的索引选择：高区分度字段
db.products.createIndex({"sku": 1}) // SKU唯一性高
// 需要谨慎的索引选择
db.users.createIndex({"gender": 1}) // 区分度低，可能效果有限
// 复合索引优化
db.orders.createIndex({"status": 1, "createdAt": -1})
六、性能考虑
索引的代价
- 写入开销：每次插入/更新都需要维护索引
- 存储空间：索引需要额外的磁盘空间
- 内存占用：索引节点可能占用缓冲池空间
索引监控与优化
// 监控索引使用情况
db.collection.aggregate([{"$indexStats": {}}])
// 删除无用索引
db.collection.dropIndex("index_name")
索引是数据库性能优化的关键工具，但需要根据具体的数据特性和查询模式进行合理设计和维护。正确的索引策略可以大幅提升查询性能，而过度索引或不当索引则可能成为性能瓶颈。