转载至 索引结构
BTree索引
B-Tree定义
- 根节点至少包括两个孩子
- 树中每个节点最多含有m个孩子( m>=2 )
- 除根节点和叶节点外,其他每个节点至少有ceil(m/2)个孩子
- 所有叶子节点都位于同一层
B+ Tree定义
B+树是B树的变体,其定义基本与B树相同,除了:
- 非叶子节点的子树指针与关键字个数相同
- 非叶子节点的子树指针P[i] ,指向关键字值[K[i], K[i+ 1])的子树
- 非叶子节点仅用来索引,数据都保存在叶子节点中
- 所有叶子节点均有一个链指针指向下一个叶子结点 (用于支持范围统计,直接从叶子节点横向统计)
B+Tree更适合用来做存储索引
- B+树的磁盘读写代价更低
- B+树的查询效率更加稳定
- B+树更有利于对数据库的扫描
其他索引结构
Hash索引
缺点
- 仅仅能满足“=”, “IN”,不能使用范围查询
- 无法被用来避免数据的排序操作
- 不能利用部分索引|键查询
- 不能避免表扫描
- 遇到大量Hash值相等的情况后性能并不一定就会比B-Trea索引高
full-text全文索引
R-Tree索引