我有一个带有DATE列的表，我想在该列上建立索引。但我碰巧知道该列中的值是按顺序分配的。我想Mariadb默认使用B树。这会有问题吗？在过去，这可能会在索引中创建“藤蔓”，并降低性能。我们正在编写where date > (some date)查询一棵藤是一个退化的树结构。想象一下这棵二叉树，1是根。这是一棵有效的二叉树，但是因为值是按顺序插入的，所以没有“树”，只有“藤”;一行节点。1 -〉2 -〉3 -〉4 -〉...
where date > (some date)
62lalag41#
B树不是二叉树，B树是自平衡的（近似）。也就是说，所有到叶节点的路径趋向于具有相同的长度。插入新条目，无论是在末端还是在中间，都将根据插入算法的性质自动重新平衡树。这包括分裂树中的非末端节点和移动树以选择新的根节点。因此从根分支出来的每个子分支具有近似相等的树的子集。如果说有什么不同的话，那就是按顺序插入到B树中 * 有助于 * 使树更紧凑和更有效。在这个博客中有一个很好的形象化的例子：https://www.percona.com/blog/2015/04/03/illustrating-primary-key-models-in-innodb-and-their-impact-on-disk-usage/
ozxc1zmp2#
MySQL和MariaDB使用B+树（参见维基百科）来创建大多数索引，包括PRIMARY KEY。B+树允许高效的顺序扫描，因为从一个块到“下一个”块有一个链接。树是一堆包含（通常）大约100行的块。（行=数据行或索引行。）例如，当通过AUTO_INCREMENT插入到B+树的“末端”时，在需要“块分裂”之前大约添加了99个条目。这种分裂将一个块变成了到，并在其父块中添加了一个条目，而其父块慢慢地变满。请注意，大约1%的INSERT会导致拆分。在某些块分裂过程中，树被重新平衡，树被保持平衡（我不知道细节），但是这种情况很少发生，我们不应该担心它的代价。另外，请注意，从100万行到1亿行只增加了一层BTree（从3到4）。一个有1亿个节点的二叉树大约有27层深。
PRIMARY KEY
AUTO_INCREMENT
2条答案
按热度按时间62lalag41#
B树不是二叉树，B树是自平衡的（近似）。也就是说，所有到叶节点的路径趋向于具有相同的长度。插入新条目，无论是在末端还是在中间，都将根据插入算法的性质自动重新平衡树。这包括分裂树中的非末端节点和移动树以选择新的根节点。因此从根分支出来的每个子分支具有近似相等的树的子集。
如果说有什么不同的话，那就是按顺序插入到B树中 * 有助于 * 使树更紧凑和更有效。在这个博客中有一个很好的形象化的例子：https://www.percona.com/blog/2015/04/03/illustrating-primary-key-models-in-innodb-and-their-impact-on-disk-usage/
ozxc1zmp2#
MySQL和MariaDB使用B+树（参见维基百科）来创建大多数索引，包括
PRIMARY KEY。B+树允许高效的顺序扫描，因为从一个块到“下一个”块有一个链接。树是一堆包含（通常）大约100行的块。（行=数据行或索引行。）
例如，当通过
AUTO_INCREMENT插入到B+树的“末端”时，在需要“块分裂”之前大约添加了99个条目。这种分裂将一个块变成了到，并在其父块中添加了一个条目，而其父块慢慢地变满。请注意，大约1%的INSERT会导致拆分。
在某些块分裂过程中，树被重新平衡，树被保持平衡（我不知道细节），但是这种情况很少发生，我们不应该担心它的代价。
另外，请注意，从100万行到1亿行只增加了一层BTree（从3到4）。一个有1亿个节点的二叉树大约有27层深。