面对有点乱序的插入，innodb 的碎片有多严重？

Question

假设 (field1, field2) 上有一个复合主键

另外，让 X 是一组理论的 n 个数字

插入看起来像这样：

INSERT INTO table(field1, field2)
VALUES([a number picked at random from X], [an incrementing number]);

每插入 m 个数字，从 X 中随机删除一个数字，并随机添加另一个数字。

假设 n=1000 和 m=500。换句话说，每插入 500 次，集合 X 中的一个元素就会改变，但集合 X 总是有 1000 个元素。

B+树会变得多么支离破碎？

Answer 1

在索引的情况下，碎片可能会有很大差异。然而，没有什么比将数据输入已经排序的索引更糟糕的了。

为了说明，让我们以最坏的情况 BTREE，一棵平衡二叉树。一个平衡二叉树是二叉树监测其子节点的高度，将只允许在高度的差异：

• -1 （左树节点比右树节点高）
• 0 （左树节点和右树节点高度相同）
• +1 （左树节点比右树节点短）
• 参见AVLTrees 的定义

25 多年前，我了解到将已经排序的数据输入到平衡二叉树中会导致 45% 的树节点需要旋转和重新平衡。

常识是，如果我输入数字 1-15，按如下顺序排列：

• 8、4、12、2、6、10、14、1、3、5、7、9、11、13、15
• 8、12、4、14、10、6、2、1、3、5、7、9、11、13、15
• 8、4、12、2、6、10、14、15、13、11、9、7、5、3、1
• 8、12、4、14、10、6、2、15、13、11、9、7、5、3、1

进入平衡二叉树，绝对不会发生树重新平衡。

在这种情况下，将随机数据输入到平衡二叉树中永远不会像输入已经排序的数据那样糟糕。平均而言，随机排序比顺序排序需要更少的树重新平衡。

现在，让我们从平衡二叉树转向更真实的 BTREE。BTREE 索引中的树节点通常拥有两个索引页条目的幂 + 指向较低 BTREE 节点的指针。页面拆分会在事件页面变满时发生。因此，由于页面拆分，许多早期的 BTREE 页面最终会变成半满（对此的执行将是批量插入和内存中键排序，并以尽可能少的碎片写出更紧凑的索引页面）。除了那个例外，在 BTREE 页面中插入有序数据会导致页面拆分的规律性非常小。随机插入至少比加载有序数据造成的破坏要小。

数据库

就 InnoDB 而言，您有gen_clust_index。它与内部用于跟踪行 ID 的另一种类型的索引挂钩。永远不要将 gen_clust_index 视为任何其他 BTREE。这就是 Oracle 世界所说的索引组织表。InnoDB 的列排序与 MyISAM 的处理方式非常不同，如果您尝试以特定键顺序重新排序行数据，您可以检测到显着差异。

根据MySQL Database Design and Tuning第 148,149 页

它表明，ALTER TABLE tblname ORDER BY column-list;通过对行进行物理排序，这样做将大大改善 MyISAM 表的检索。相比之下，这样做ALTER TABLE tblname ORDER BY column-list;不会对 InnoDB 表产生影响，因为数据始终按聚集键内的 RowID 排序。

故事的道德启示

说到 InnoDB，不用担心数据的随机性。无论您对表索引执行何种操作，聚集键对访问都有最终决定权。无论您加载数据的顺序如何， gen_clust_index 都会遵守它。无话可问。