概念
- 索引是一种用于快速查询和检索数据的数据结构。常见的索引结构有: B 树， B+树和 Hash。
- 索引相当于目录的作用，例如字典的目录。
优缺点
- (优点)检索速度快，检索的数据量降低。
- (优点)创建唯一性索引，可以保证数据的唯一性。
- 时间上：创建和维护索引需要时间。
- 空间上：索引需要物理文件存储，消耗一定的空间。
数据结构
Hash 表
为什么 MySQL 没有使用其作为索引的数据结构呢？
- Hash 冲突问题。
- Hash 索引不支持顺序和范围查询 ( 最大缺点 )。
B 树
一个 M 阶的 B 树（M>2）有以下的特性：
- 根节点的儿子数的范围是
[2,M]。 - 每个中间节点包含 k-1 个关键字和 k 个孩子，孩子的数量 = 关键字的数量 +1，k 的取值范围为
[ceil(M/2), M]。 - 叶子节点包括 k-1 个关键字（叶子节点没有孩子），k 的取值范围为
[ceil(M/2), M]。 - 假设中间节点节点的关键字为：
Key[1],Key[2], …,Key[k-1]，且关键字按照升序排序，即Key[i]<Key[i+1]。此时 k-1 个关键字相当于划分了 k 个范围，也就是对应着 k 个指针，即为：P[1],P[2], …,P[k]，其中P[1]指向关键字小于Key[1]的子树，P[i]指向关键字属于(Key[i-1], Key[i])的子树，P[k]指向关键字大于Key[k-1]的子树。 - 所有叶子节点位于同一层。
B+树
B+ 树和 B 树的差异：
- 有 k 个孩子的节点就有 k 个关键字。也就是孩子数量 = 关键字数，而 B 树中，孩子数量 = 关键字数+1。
- 非叶子节点的关键字也会同时存在在子节点中，并且是在子节点中所有关键字的最大（或最小）。
- 非叶子节点仅用于索引，不保存数据记录，跟记录有关的信息都放在叶子节点中。而 B 树中，非叶子节点既保存索引，也保存数据记录。
- 所有关键字都在叶子节点出现，叶子节点构成一个有序链表，而且叶子节点本身按照关键字的大小从小到大顺序链接。
B+树，叶子内单向链表，叶子之间双向链表。
B 树 & B+树
B 树也称 B-树, 全称为 多路平衡查找树 ，B+ 树是 B 树的一种变体。B 树和 B+树中的 B 是 Balanced （平衡）的意思。
目前大部分数据库系统及文件系统都采用 B-Tree 或其变种 B+Tree 作为索引结构。
B 树& B+树两者有何异同呢？
- B 树的所有节点既存放键 (key) 也存放数据 (data)，而 B+树只有叶子节点存放 key 和 data，其他内节点只存放 key。
- B 树的叶子节点都是独立的; B+树的叶子节点有一条引用链指向与它相邻的叶子节点。
- B 树的检索的过程相当于对范围内的每个节点的关键字做二分查找，可能还没有到达叶子节点，检索就结束了。而 B+树的检索效率就很稳定了，任何查找都是从根节点到叶子节点的过程，叶子节点的顺序检索很明显。
R 树
R-Tree 在 MySQL 很少使用，仅支持 geometry 数据类型，支持该类型的存储引擎只有 myisam 、 bdb 、 innodb 、 ndb 、 archive 几种。
举个 R 树在现实领域中能够解决的例子：查找 20 英里以内所有的餐厅。如果没有 R 树你会怎么解决？一般情况下我们会把餐厅的坐标(x,y)分为两个字段存放在数据库中，一个字段记录经度，另一个字段记录纬度。这样的话我们就需要遍历所有的餐厅获取其位置信息，然后计算是否满足要求。如果一个地区有 100 家餐厅的话，我们就要进行 100 次位置计算操作了，如果应用到谷歌、百度地图这种超大数据库中，这种方法便必定不可行了。R 树就很好的解决了这种高维空间搜索问题。它把 B 树的思想很好的扩展到了多维空间，采用了 B 树分割空间的思想，并在添加、删除操作时采用合并、分解结点的方法，保证树的平衡性。
因此，R 树就是一棵用来存储高维数据的平衡树。相对于 B-Tree，R-Tree 的优势在于范围查找。