数据库索引中包含的数据结构有哪些

1 索引介绍
　　MySQL官方对索引的定义为：索引(Index)是帮助MySQL高效获取数据的数据结构。提取句子主干，就可以得到索引的本质：索引是数据结构。
　　我们知道，数据库查询是数据库的最主要功能之一，例如下面的SQL语句：

SELECT * FROM my_table WHERE col2 = '77'

　　可以从表“my_table”中获得“col2”为“77”的数据记录。
　　我们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找(linear search)，遍历“my_table”然后逐行匹配“col2”的值是否是“77”，这种复杂度为O(n)的算法在数据量很大时显然是糟糕的，好在计算机科学的发展提供了很多更优秀的查找算法，例如二分查找(binary search)、二叉树查找(binary tree search)等。如果稍微分析一下会发现，每种查找算法都只能应用于特定的数据结构之上，例如二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上，但是数据本身的组织结构不可能完全满足各种数据结构(例如，理论上不可能同时将两列都按顺序进行组织)，所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用(指向)数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。
　　看一个例子：

图 1

图 2

BTree_Search(node, key) 
{ 
    if(node == null) return null; 
    foreach(node.key) 
    { 
        if(node.key[i] == key) return node.data[i]; 
        if(node.key[i] > key) return BTree_Search(point[i]->node); 
    } 
        return BTree_Search(point[i+1]->node); 
} 
    data = BTree_Search(root, my_key); 

　　关于B-Tree有一系列有趣的性质，例如一个度为d的B-Tree，设其索引N个key，则其树高h的上限为logd((N+1)/2)，检索一个key，其查找节点个数的渐进复杂度为O(logdN)。从这点可以看出，B-Tree是一个非常有效率的索引数据结构。
　　另外，由于插入删除新的数据记录会破坏B-Tree的性质，因此在插入删除时，需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质，本文不打算完整讨论B-Tree这些内容，因为已经有许多资料详细说明了B-Tree的数学性质及插入删除算法，有兴趣的朋友可以在本文末的参考文献一栏找到相应的资料进行阅读。
　2.1 B+Tree
　　B-Tree有许多变种，其中最常见的是B+Tree，例如MySQL就普遍使用B+Tree实现其索引结构。
　　与B-Tree相比，B+Tree有以下不同点：
　　每个节点的指针上限为2d而不是2d+1。
　　内节点不存储data，只存储key;叶子节点不存储指针。
　　图3是一个简单的B+Tree示意。

图 3

图 4

图 5

图 6

图 7

　　转自博客：
　　http://www.cnblogs.com/leoo2sk/archive/2011/07/10/mysql-index.html