MySql教程

mysql为什么用B+树做索引

本文主要是介绍mysql为什么用B+树做索引,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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

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

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

  • 1.非叶子节点只存储键值信息;
  • 2.所有叶子节点都有一个链指针;
  • 3.数据记录都放在叶子节点中;
这篇关于mysql为什么用B+树做索引的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!