主流索引查找算法

  • 线性查找 Linear Search
  • 二分查找 Binary Search
  • 二叉查找树 Binary Search Tree
  • 平衡二叉树 AVL Tree
  • B树 B Tree

  • B+树 B+ Tree

    线性查找 Linear Search

  • 时间复杂度O(N)

  • 从第一个数据开始，逐个匹配

    二分查找 Binary Search

  • 时间复杂度O(logN)

  • 去看数据结构与算法吧

    二叉查找树

  • 时间复杂度O(logN)

  • 使用经典的二叉树数据结构
  • 由根节点开始查找

  • 可能退化为线性查找

    平衡二叉树AVL Tree

  • 带有平衡因子，如果打破了平衡因子，就会有旋转的操作

  • 去看数据结构与算法吧
  • 查找跟二叉查找树一样

  • 保证不会退化成线性查找

    B树 B Tree

    image.png

  • B树是线性数据结构和树的结合

  • 多数据节点降低了树的高度

  • B树不需要旋转就可以保证树的平衡

    B+树 B+ Tree

    image.png

  • B+树是由树发展而来的一种数据结构

  • B+树的所有数据均在叶子节点

  • B+树的所有数据形成了一个线性表

    总结

  • B+树是目前最主流的数据库索引算法

  • B+树由线性表、二叉树、B树发展而来
  • B+树集成了线性表、平衡二叉树的优势