索引可选数据结构

• 二叉树
• 红黑树
• hash(散列)
• B Tree

Q:MySQL 不用二叉树/红黑树的原因

A:二叉树在 左/右 子节点占比偏差过大的时候会变为链表; 红黑树的树高存在过高的情况, 检索效率低.

B Tree

• 从根节点到达所有叶节点的高度相同, 叶节点指针为空
• 所有叶节点不同
• 节点数据从左到右递增排序

这种数据结构对于检索单列的情况足够使用, 但是SQL中还存在较多的范围查找(>、<), 所以引入下面的B+树来做优化.

B+ Tree

摘要

• 非叶子节点不存储data(eg: 对于聚簇索引来说，这个data就相当于行数据的内存地址), 只存储索引
• 叶子结点包含所有所有索引 & 索引对应的数据
• 叶子结点从左到右(从右到左)用指针链接成双向链表便于正序和倒序形式的检索
• 检索的时候可以直接从上至下进行检索, 不必每个节点都遍历完全, 因为数据都在叶子结点上
• 数据的拼接排序也可以直接从B+Tree的底层的双层链表开始进行处理, 而不必在非叶子节点上进行不必要的I/O

如果我们要进行范围内的数据搜索, 只需要从叶子结点的某一处节点开始处, 检索到某一处叶子节点的终止处即可.

概念图

>>> To Be Continued…

数据结构 – 页

"页" 是MySQL的存储单位, 每个B+ Tree的叶子节点都是由n个页构成, 默认一页大小为16K. 头部信息中存储有类型、唯一标识符、前后节点信息等.