MySQL索引和数据访问时间复杂度

Question

在MySQL中，我读到由于使用BTree而在特定数据列上建立索引时，数据访问时间复杂度为log(n)，请问是否存在任何情况下数据访问时间变得比log(n)多的情况？ C0]，因为当我们以排序方式将数据插入到BTree中时，树会在一侧增长，并且数据访问复杂度会增长到O(n)，那么他们是否有任何将数据插入此索引BTree的策略？感谢您的回答

Answer 1

一些注意事项：

• 磁盘访问对性能而言比O（）重要得多。
• “经验法则”：一个节点有100个子节点（或叶元素）。因此...
• 在典型的InnoDB BTree（数据或索引）中，一百万行的表将只有大约3个级别。对于trillion行，大约有6个级别。这是“ log n”起作用的主要位置。
• B树，如果自下而上，则保持平衡。
• 在MySQL中，不必担心BTree；还有更糟糕的事情要处理-索引编制，查询编制等。
• [InnoDB使用O(n)，由于每次树耗尽节点的元素时都不必对树进行挖掘，因此使索引扫描变得相当有效。
• Wikipedia是另一个有用的参考。