一, 定义
索引定义: 索引 (Index) 是帮助 MySQL 高效获取数据的数据结构.
本质: 索引是数据结构.
二, B-Tree
m 阶 B-Tree 满足以下条件:
每个节点至多可以拥有 m 棵子树.
根节点, 只有至少有 2 个节点(要么极端情况, 就是一棵树就一个根节点, 单细胞生物, 即是根, 也是叶, 也是树).
非根非叶的节点至少有的 Ceil(m/2)个子树(Ceil 表示向上取整, 如 5 阶 B 树, 每个节点至少有 3 个子树, 也就是至少有 3 个叉).
非叶节点中的信息包括[n,A0,K1,A1,K2,A2,...,Kn,An],, 其中 n 表示该节点中保存的关键字个数, K 为关键字且 Ki<Ki+1,A 为指向子树根节点的指针.
从根到叶子的每一条路径都有相同的长度(叶子节点在相同的层)
B-Tree 特性:
关键字集合分布在整颗树中;
任何一个关键字出现且只出现在一个节点中;
每个节点存储 date 和 key;
搜索有可能在非叶子节点结束;
一个节点中的 key 从左到右非递减排列;
所有叶节点具有相同的深度, 等于树高 h.
三, B+Tree
B+Tree 与 B-Tree 的差异在于:
B+Tree 非叶子节点不存储 data, 只存储 key;
所有的关键字全部存储在叶子节点上;
每个叶子节点含有一个指向相邻叶子节点的指针, 带顺序访问指针的 B + 树提高了区间查找能力;
非叶子节点可以看成索引部分, 节点中仅含有其子树 (根节点) 中的最大 (或最小) 关键字;
四, B/B + 树索引的性能分析
依据: 使用磁盘 I/O 次数评价索引结构的优劣
主存和磁盘以页为单位交换数据, 将一个节点的大小设为等于一个页, 因此每个节点只需一次 I/O 就可以完全载入.
根据 B 树的定义, 可知检索一次最多需要访问 h 个节点
渐进复杂度: O(h)=O(logdN)
dmax=floor(pagesize/(keysize+datasize+pointsize))
一般实际应用中, 出度 d 是非常大的数字, 通常超过 100, 因此 h 非常小(通常不超过 3,3 层可存大约一百万数据)
B-Tree 中一次检索最多需要 h-1 次 I/O(根节点常驻内存)
B+Tree 内节点不含 data 域, 因此出度 d 更大, 则 h 更小, I/O 次数少, 效率更高, 故 B+Tree 更适合外存索引.
五, MySQL 索引实现
1. MyISAM 引擎使用 B+Tree 作为索引结构, 叶节点的 data 域存放的是数据记录的地址; MyISAM 主索引和辅助索引在结构上没有任何区别, 只是主索引要求 key 是唯一的, 而辅助索引的 key 可以重复;
2. InnoDB 的数据文件本身就是索引文件, 叶节点包含了完整的数据记录, 这种索引叫做聚集索引. 因为 InnoDB 的数据文件本身要按主键聚集, 所以 InnoDB 要求表必须有主键(MyISAM 可以没有), 如果没有显式指定, 则 MySQL 系统会自动选择一个可以唯一标识数据记录的列作为主键, 如果不存在这种列, 则 MySQL 自动为 InnoDB 表生成一个隐含字段作为主键.
InnoDB 的辅助索引 data 域存储相应记录主键的值而不是地址;
辅助索引搜索需要检索两遍索引: 首先检索辅助索引获得主键, 然后用主键到主索引中检索获得记录;
3. 页分裂问题
如果主键是单调递增的, 每条新记录会顺序插入到页, 当页被插满后, 继续插入到新的页;
如果写入是乱序的, InnoDB 不得不频繁地做页分裂操作, 以便为新的行分配空间. 页分裂会导致移动大量数据, 一次插入最少需要修改三个页而不是一个页.
如果频繁的页分裂, 页会变得稀疏并被不规则地填充, 所以最终数据会有碎片.
六, 总结
了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助
为什么不建议使用过长的字段作为主键?
为什么选择自增字段作为主键?
为什么常更新是字段不建议建立索引?
为什么选择区分度高的列作为索引? 区分度的公式是 count(distinct col)/count(*)
尽可能的使用覆盖索引
来源: http://www.bubuko.com/infodetail-2944498.html