索引就像是书或者论文的目录, 通过目录能够快速定位到某一章节, 加快了查找的效率, 减少插入和删除操作; 那么知道索引是干啥的了, 那索引的底层数据结构是什么呢???

1 简述

  如果数据库中没有索引, 查找的时候就会遍历整个表; 如果针对的是顺序表查找, 因为顺序表在内存中, 访问速度比较快, 而且数据也没那么多, 效率还是可以的; 但是如果针对数据库进行顺序查找, 数据库的数据都存在磁盘上, 磁盘的访问速度会很慢, 并且数据量也会很多, 这时候查找的效率就非常低. 而索引就是为了避免数据库进行顺序查找, 提高了查找效率.

2 索引考虑的数据结构

  关于索引的数据结构肯定首先想到的是二叉搜索树或者是哈希表, 对于二叉搜索树如果比较平衡, 那么查找的效率为 O(logN); 如果是哈希表则查找效率为 O(1);

  其实数据库的索引也可以考虑使用哈希表, 但是会存在问题, 毕竟是一对一的关系, 只能处理相等的情况, 如果遇到 id > 3 且 id < 9 这种情况, 这时候哈希表就不适用了.

  二叉搜索树的内部元素是有序 (中序遍历), 例如还是查找 id > 3 且 id < 9 的情况, 具体流程: 先找到 id 为 9 的元素, 再找到 id 为 3 的元素, 中序遍历中 3 和 9 之间的结果就是想要的结果, 效率为 O(N); 相比于哈希表, 二叉搜索树虽然能够处理范围查找, 但是处理效率并不高:

• 二叉搜索树每个节点最多有两个分叉, 当数据量比较大的时候树的高度就会很高, 最终的效率也会很低;

• 二叉搜索树直接获取到中序遍历也不是很高效, 为 O(N).

因此真实的索引结构是 N 叉搜索树, 也就是 B+ 树, 和 B 树相比, 主要两个功能发生了变化:

• 每一层的元素之间都链接到了一起;
• 数据只在叶子节点上保存, 非叶子节点上只保存一些辅助查找的边界信息 (也就是说非叶子节点只保存 id, 辅助快速找到想要的 id 对应的节点).

针对 N 叉搜索树查询任何一条记录速度是比较平均的, 不会出现效率差异大的情况, 不需要进行额外的中序遍历; 并且叶子节点放在磁盘上, 非叶子节点放在内存中 (B 树的叶子节点 / 非叶子节点都放在磁盘上存储数据), 这样查找效率就会更高, 减少了读磁盘的次数, 毕竟索引在内存中占用的实际开销也不是很高.