深入学习InnoDB（3）—索引存储结构分析

1. 索引的各种存储结构及其优缺点

1.1 二叉树

优点：
二叉树相较于顺序查找方式更为高效地实现数据查找功能。其核心原理是通过与根节点进行比较来确定搜索方向：若等于当前节点值，则直接返回该节点位置；当目标元素值小于当前节点值时，则转向左子树继续查找；反之亦然，在右子树中继续执行相同步骤直至找到目标元素所在的位置。

缺点：

通常情况下，在创建表时我们会为建立索引预先分配一个自增整型字段。然而，在这种场景下采用二叉树结构会导致这些自增字段总是被附加到右侧列上，并不会提升查找记录的效果与未添加任何额外键值的行为相异。

1.2 红黑树

1. 优点：

被称为平衡二叉树的数据结构，并非传统意义上的二叉搜索树（BST），它的高度始终保持在最低水平上以实现高效的查找性能。BST虽然简单易懂但存在不足之处例如无法直接支持范围查询操作；而通过动态图可以看到红黑树会通过左旋或右旋调整结构以保持平衡从而满足左子节点数小于父节点数小于右子节点数这一核心性质

2. 缺点：

当数据量增大时，在这种情况下树的深度也随之增加

1.3 Hash

1. 优点：

对数据执行哈希运算，在实际应用中常用到的主要几种算法包括MD5、SHA-256等技术方案。随后会利用计算得到的哈希值作为中间桥梁连接索引信息与原始存储位