数据结构 之 索引技术（线性、倒排、动态检索B+、位索引、红黑树）

转自：http://blog.csdn.net/moonboat0331/article/details/10187505

线性索引

定义：按照关键码的顺序进行排序，文件中的指针指向存储在磁盘上的文件记录起始位置或者主索引中主码的起始位置。

优点：可以对变长数据库记录访问，对数据进行高效检索，例如二分检索；顺序处理：比较操作、批处理的操作；节省空间 (相对其它索引结构)

缺点：线性索引太大，存储在磁盘中：在一次检索过程中可能多次访问磁盘，从而影响检索的效率；使用二级线性索引；更新线性索引，例如在数据库中插入或者删除记录时

静态索引

索引结构在文件创建、初始装入记录时生成，一旦生成就固定下来，在系统运行(例如插入和删除记录)过程中索引结构并不改变。

一般组织索引采用多分树来减少对外存的访问次数

ISAM，采用B+树

倒排索引

对某属性按属性值建立索引表，称倒排表，属性是离散型，对于连续型的要使用B+树；缺点，需要多余的空间存储倒排表，降低了更新运算的效率。

动态索引（B、B+树）

上图是一个2-3阶B树

(1)每个结点至多有m个子结点；
(2)除根结点和叶结点外，其它每个结点至少有m/2（向上取整）个子结点；
(3)根结点至少有两个子结点：唯一例外的是根结点就是叶结点时没有子结点，此时B树只包含一个结点
(4)所有的叶结点在同一层；
(5)有k个子结点的非根结点恰好包含k-1个关键码。
B树把（值接近）相关记录放在同一个磁盘页中，从而利用了访问局部性原理；B树保证树中至少有一定比例的结点是满的，这样能够改进空间的利用率，减少检索和更新操作的
o可以容纳m个(关键码，子结点页块指针) ，假设关键码所占字节数与指针相同
n可以容纳B树的(关键码，隐含指针，子结点页块指针)最多为2m/3(B树为0.67m阶)。
o假设B树充盈度也是75％，则B树结点有0.5m个子结点
oB树的高度为

B树：一种平衡的多分树，结构定义：

优点：

磁盘读取数目。

树高为h时，插入最多需要的读写次数为3h+1

B+树

与B树的区别在于有k个子结点的结点必有k个关键码。每个节点上都有关键码信息，各层节点关键码均是下一层的最大或最小值。叶节点一般链接起来，形成一个双链表，也可以顺序查找。

相比于B树，B+树的存储更为高效，插入删除也更为方便，因此使用更广泛。

假设一个主文件有N个记录，假设一个页块可以存m个(关键码，子结点页块地址)二元对

假设B+树平均每个结点有0.75m个子结点，充盈度为(1+0.5)/2= 75％

因此B+树的高度为

位索引技术

B树适合于查找并取回少量记录的情况，对于数据仓库的复杂交互式查询，B树有三个缺点：
nB树对唯一值极少的（低基数）数据字段几乎毫无价值
n在数据仓库中构造和维护索引的代价高
n对于带有分组及聚合条件的复杂查询无能为力
倒排表可以使用位图简化。

红黑树

定义：根特征：根结点永远是“黑色”的；外部特征：扩充外部叶结点都是空的“黑色”结点；
内部特征： “红色”结点的两个子结点都是“黑色”的
不允许两个连续的红色结点
深度特征：任何结点到其子孙外部结点的每条简单路径都包含相同数目的“黑色”结点
节点的阶：
结点X的阶（rank，也称“黑色高度”）：从该结点到外部结点的黑色结点数量，不包括X结点本身，包括叶结点
外部结点的阶是零
根的阶称为该树的阶
性质：
1、红黑树是满二叉树
2、阶为k的红黑树路径长度最短是k，最长是2k：从根到叶的简单路径长度即树高最小是k+1，最长是2k+1
4、n个内部结点的红黑树树高，最大是2 log (n+1)+1
AVL树要求完全平衡
RB-Tree局部平衡，统计性能好于AVL树，且增删记录算法性能好、易实现
C++STL的set、multiset、map、multimap都应用了红黑树的变体

3、阶为k的红黑树的内部结点，最少是一棵完全满二叉树，内部结点数最少是2^k-1