二叉树

二叉树在查找目标元素的时候,首先从父节点开始和目标元素比较。如果相等那么就返回当前节点, 如果目标节点小于当前节点, 则移动到左侧节点进行比较, 反之移动到右侧节点比较。最终找到目标节点。
但是很多情况下, 很多索引列的选择会选择自增字段(主键)。那么索引建立的时候总是添加到右侧，效果和没有索引是一样的。 —> 不适合做数据库索引
image.png

红黑树

红黑树也叫平衡二叉树,继承了二叉树的优点, 并且解决了二叉树索引自增的问题。红黑树会对结果进行调整, 始终保持左子节点 < 父节点 < 右节点。但是其实每一个父节点只有两个子节点, 当数据量很大时候, 树的深度也很大.
image.png
同样不适合做数据库索引

B-tree

在红黑树基础上做优化, 适当的增加每个父节点存储的数据个数即可。(数据个数也是有一个阈值的 -> 也叫度) 节点存储个数大于度 就会自动分裂。
树节点结构:
image.png
上图为树节点结构, 首先每一个节点上保存了两部分数据, 索引值以及表记录信息。其次节点数据中的key从左到右依次是递增的。
image.png

B+tree(MYSQL索引真正的存储结构)

为什么要在B-tree的基础上再优化:
对于索引值和表数据是存储在文件中的, 当进行查询的时候, 是内存中查找的. 找到了直接使用,找不到从磁盘读取。操作系统存储数据最小单位是页(4K). 在B-tree中一个节点既存放了索引值又存放了表数据。 其实一个节点大小很大(10M). 那么我们就需要10M / 4K = 2500次的IO。这个效率很低的。
B+tree优化:叶节点只存储索引值, 子节点存储索引值和数据。这样可以在单个节点上存放更多的索引值。提高命中率。当然这种结构会在上层叶子节点上存在冗余。但是冗余的是索引数据, 占用内存很少的。
image.png
PS:每一个叶子节点都指向下一个叶子节点。