对于索引, 我们都知道其可以提高数据查询的效率, 也都知道他像查字典的26个字母或者偏旁部首一样, 但是他的底层的真正数据结构是什么?
MySQL索引的数据结构是B+树
B+树和B树相同点:
- 根节点至少一个元素
- 非根节点元素范围(m阶树): m/2 <= k <= m-1
B+树和B树非常相似, 不同点:
- B+树有两种类型的节点, 内部节点和叶子节点, 内部节点不存数据信息, 只存索引; 叶子节点存储数据信息;
- 每个叶子节点都含有左右节点的指针, 叶子节点按照关键字的大小自小而大顺序排列
- 父节点存有右孩子第一个元素的索引.
B+树的插入和删除都比B树简单.
B树和B+树对比
- 同一大小的磁盘页, B+树单一节点存储的元素更多(因为数据节点都存储在叶子节点, 而B树各个节点都含有数据元素), 使得查询的IO次数更少
- 所有查询都要查到叶子节点, 查询性能更稳定
- 所有叶子节点形成有序链表, 便于范围查询