MySQL 索引数据结构 B+ Tree 和 Hash
索引数据结构
B Tree
B Tree 是一种多叉平衡查找树
特点
- B树的节点中存储这多个元素，每个内节点有多个分叉。
- 通过增加树的分叉树，将树的体型从高瘦变成了矮胖。
- 比二叉树效率高，因为减少了磁盘 IO 次数（加载每个节点需要一次 IO）。
- 节点中的元素包含键值和数据，节点中的键值从大到小排列。也就是说，在所有的节点中都存储数据。
- 构建1百万条数据，树的高度需要2层就可以（1000*1000=1百万），也就是说只需要两次磁盘IO操作就可以查询到数据
- 父节点当中的元素不会出现在子节点中
- 所有的叶子节点都位于同一层，叶子节点具有相同的深度，叶子节点之间没有指针连接
结构
查找流程
存在问题
- B树不支持范围查询的快速查找
- 查询10到35之间的数据，查找到10之后，需要回到根节点重新遍历查找，需要从根节点进行多次遍历，查询效率有待提高
- 如果data存储的是行记录，行的大小随着列数的增加，所占空间会变大
- 这时一页中可存储的数据量就会减少，树相应就会变高，磁盘IO次数就会随之增加
B+ Tree
MySQL 在 B 树的基础上进行改造，使用 B+ 树构建索引
特点
- B树
- 叶子节点和非叶子节点都会存储数据
- B+树
- 只有叶子节点才会存储数据，非叶子节点只存储键值key
- 叶子节点之间使用双向指针连接，最底层的叶子节点形成了一个双向有序链表
结构
查找流程
Hash
底层是哈希表：
- 适用于大多数需求都是单条记录查询
- 不支持范围快速查找，范围查找时只能通过扫描全表的方式，筛选出符合条件的数据
- Key 可以存储索引列，Value 可以存储行记录或者行磁盘地址