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

Question

在MySQL我读到，当我们对特定数据列进行索引时，数据访问时间复杂度是log(n)因为使用了 BTree，是否存在数据访问时间变得更多的情况，log(n)例如O(n)，因为当我们以排序方式将数据插入 BTree 时树在一侧增长并且数据访问复杂性增长到O(n)他们是否有将数据插入此索引 BTree 的任何策略？谢谢回答

标签： mysqlindexingtimecomplexity-theory

Answer 1

需要注意的一些事项：

• 磁盘访问（对性能）远比 O() 重要。
• “经验法则”：一个节点有 100 个子节点（或叶元素）。因此...
• 在典型的 InnoDB BTree（数据或索引）中，一百万行的表只有大约 3 层深。对于一万亿行，大约 6 个级别。这是“log n”发挥作用的主要地方。
• BTrees，如果自下而上增强，保持平衡。
• 在 MySQL 中，不用担心 BTree；还有更糟糕的事情需要处理——索引、查询的制定等。
• InnoDB 使用B+Trees，通过不必在每次耗尽节点的元素时都向下钻取树，从而使索引扫描相当有效。
• 维基百科是另一个有用的参考。