mysql索引采用什么数据结构

文就是对这两种数据结构做简单的介绍。

1. B-Tree

B-Tree不是“B减树”，而是“B树”。

这里参考了严蔚敏《数据结构》对B-Tree的定义：

一棵m阶的B-Tree,或者为空树，或者满足下列特性：

1.树中每个结点至多有m棵子树；

2.若根结点不是叶子结点，则至少有两棵子树；

3.除根节点之外的所有非终端结点至少有[m/2]棵子树；

4.所有非终端结点中包含下列信息数据:

(n,A0,K1,A1,K2,A2……Kn,An)

其中，n为关键字的数目，K(i)为关键字，且K(i) <K(i+1), Ai为指向子树根结点的指针，且指针A(i-1)所指子树中所有结点的关键字均小于Ki，Ai所指子树中所有结点的关键字均大于Ki；

5.所有叶子结点都出现在同一层次上；

下面通过一个例子解释一下B-Tree的查找过程。

这是一棵4阶的B-Tree，深度为4。

假如在该图中查找关键字47，首先从根结点开始，根据根结点指针t找到*a结点，因为47大于 *a 结点的关键字35，所以会去A1指针指向的 *c结点继续寻找，因为 *c的关键字 43 <要查找的47 <*c结点的关键字78，所以去 *c结点A1指针指向的 *g结点去寻找，结果在 *g结点中找到了关键字47，查找成功。

2. B+Tree

不同的存储引擎可能使用不同的数据结构存储，InnoDB使用的是B+Tree；那什么是B+Tree呢？

B+Tree是应文件系统所需而出的一种B-Tree的变型树，一棵m阶的B+树和m阶的B-树的差异在于:

1.有n棵子树的结点中含有n个关键字；

2.所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字的记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接；

3.所有的非终端结点可以看成是索引部分，结点中仅含有其子树(根结点)中的最大（或最小）关键字；

还是通过一个例子来说明。

这个例子中，所有非终端结点仅含有子树中最大的关键字。

因为叶子节点本身依据关键字的大小自小而大顺序链接，所以可以从最小关键字起顺序查找。也可以从根结点开始，进行随机查找。

在B+树中随机差找和在B-树中类似，以上图为例。假设要查找关键字51，现在根节点中比较，发现51<59，因为这里使用的是非终端结点的关键字是子树中最大的关键字，所以进入最大值为59的子结点(15\44\59)中查找，同理，因为44<51<59，所以进入P3指向的结点(51\59)中查找，然后命中关键字51，因为此结点(51\59)是叶子结点，所以查找终止，该结点包含指向数据的指针。

3.索引如何在B+Tree中组织数据存储

假设有如下表:

对于表中的每一行数据，索引中包含了last_name、first_name和dob列的值，下图展示索引是如何组织数据存储的:

索引对多个值进行排序的依据是定义索引时列的顺序。

(Allen Cuba 1960-01-01)结点左侧的指针指向[?,Allen Cuba 1960-01-01)的叶子页，(Allen Cuba 1960-01-01)和(Astaire,Angelina,1980-03-04)之间的指针指向[Allen Cuba 1960-01-01,Astaire Angelina 1980-03-04)的叶子页，以此类推。总之，每个指针指向的结点中的最小值就是该指针左侧的的值。

这种存储结构也说明了在定义多个列组成的多列索引中，为什么需要把重复率最低的列放到最左侧，因为这会减少比较的次数，查找起来更加高效。

4.索引为什么选用B树这种数据结构？

因为使用B树查找时，所用的磁盘IO *** 作次数比平衡二叉树更少，效率也更高。

为什么使用B树查找所用的磁盘IO *** 作次数比平衡二叉树更少？

大规模数据存储中，树节点存储的元素数量是有限的（如果元素数量非常多的话，查找就退化成节点内部的线性查找了），这样导致二叉查找树结构由于树的高度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下。那么我们就需要减少树的高度以提高查找效率。而平衡多路查找树结构B树就满足这样的要求。B树的各种 *** 作能使B树保持较低的高度，从而达到有效减少磁盘IO *** 作次数。

谈到索引，大家并不陌生。索引本身是一种数据结构，存在的目的主要是为了缩短数据检索的时间，最大程度减少磁盘 IO。

任何有数据的场景几乎都有索引，比如手机通讯录、文件系统（ext4\xfs\ntfs)、数据库系统（MySQL\Oracle）。数据库系统和文件系统一般都采用 B+ 树来存储索引信息，B+ 树兼顾写和读的性能，最极端时检索复杂度为 O(logN)，其中 N 指的是节点数量，logN 表示对磁盘 IO 扫描的总次数。

MySQL 支持的索引结构有四种：B+ 树，R 树，HASH，FULLTEXT。

B 树是一种多叉的 AVL 树。B-Tree 减少了 AVL 数的高度，增加了每个节点的 KEY 数量。

B 树的特性：（m 为阶数：结点的孩子个数最大值）

1. 树中每个节点最多含有 m 个孩子节点 (m>=2)；

2. 除根节点和叶子结点外，其他节点的孩子数量 >=ceil(m / 2)；

3. 若根节点不是叶子结点，最少有两个孩子

特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点；

4. 每个非叶子结点中包含有 n 个关键字信息：(n，P0，K1，P1，K2，P2，......，Kn，Pn) 其中：

Ki (i=1...n) 为关键字，且关键字按顺序升序排序 K(i-1)<Ki

Pi 为指向儿子节点的指针，且指针 P(i-1) 指向的儿子节点里所有关键字均小于 Ki，但都大于 K(i-1)

关键字的个数 n 必须满足：[ceil(m / 2)-1]<= n <= m-1

如果一个结点有 n 个关键字，那么该结点有 n+1 个分支。这 n+1 个关键字按照递增顺序排列

所有叶子结点都出现在同一层，是所有遍历的终点位置

你是想说MYSQL的记录指针吧？那也就是记录集游标，是在一个记录集里面标识当前记录的一个标识，比如你SELECT 出来20条记录，如果你不循环20次的话你是取不出这20条记录的，因为记录集游标没有动，始终指向的是第一条记录，所以一般取所有记录的写法都是while(false == $Rows = mysql_fetch_row($query)) {}，不知道，现在清楚没有？

---