BTree索引

B-Tree定义

  • 根节点至少包括两个孩子
  • 树中每个节点最多含有m个孩子( m>=2 )
  • 除根节点和叶节点外,其他每个节点至少有ceil(m/2)个孩子
  • 所有叶子节点都位于同一层

image.png
image.png

B+ Tree定义

image.png
B+树是B树的变体,其定义基本与B树相同,除了:

  • 非叶子节点的子树指针与关键字个数相同
  • 非叶子节点的子树指针P[i] ,指向关键字值[K[i], K[i+ 1])的子树
  • 非叶子节点仅用来索引,数据都保存在叶子节点中
  • 所有叶子节点均有一个链指针指向下一个叶子结点 (用于支持范围统计，直接从叶子节点横向统计)

B+Tree更适合用来做存储索引

  • B+树的磁盘读写代价更低
  • B+树的查询效率更加稳定
  • B+树更有利于对数据库的扫描

其他索引结构

Hash索引

image.png

缺点

  • 仅仅能满足“=”, “IN”，不能使用范围查询
  • 无法被用来避免数据的排序操作
  • 不能利用部分索引|键查询
  • 不能避免表扫描
  • 遇到大量Hash值相等的情况后性能并不一定就会比B-Trea索引高

    full-text全文索引

    R-Tree索引

位图索引

image.png