mysql为什么用B+树做索引

为什么不用hash,二叉树,平衡二叉树(AVL),B-树呢?InnoDB并不支持hash索引

  • 1.hash的时间复杂度是O(1),但是会退化为O(n),而且无法解决排序,范围查询等问题;
  • 2.树的时间复杂度是O(log2(n));比O(n)小,所以排除hash;
  • 3.二叉树的特点是
    mysql为什么用B+树做索引
  • 4.二叉树会产生的问题(由于不平衡,所以会右倾或者左倾,又退化成链表,复杂度从O(log2(n))变成O(n))
    mysql为什么用B+树做索引
  • 5.平衡二叉树确实可以减少查询次数,但是当数据量很大,那么树高就会很高(磁盘IO就很大),也是不利于查找的;那么可以通过减少树的高度,变成矮胖树,来减少磁盘IO;
  • 6.B树又叫二三树(B树比平衡二叉树减少一次IO);
    mysql为什么用B+树做索引
    InnoDB默认磁盘页是16KB
    mysql为什么用B+树做索引
    mysql为什么用B+树做索引
    B树检索原理
    mysql为什么用B+树做索引
    mysql为什么用B+树做索引
  • 7.B+树
    结构图
    mysql为什么用B+树做索引
    中序遍历
    mysql为什么用B+树做索引
    检索原理
    mysql为什么用B+树做索引
    mysql为什么用B+树做索引

B+树相对于B树有几点不同呢?

  • 1.非叶子节点只存储键值信息;
  • 2.所有叶子节点都有一个链指针;
  • 3.数据记录都放在叶子节点中;

mysql为什么用B+树做索引

上一篇:让hangfire的ASP.NET Core 应用程序在IIS上始终运行


下一篇:《用友ERP-U8(V8.72)模拟实战----财务、供应链和生产制造》一导读