数据库之MySQL索引

MySQL官方对索引的定义为：
索引（Index）是帮助MySQL高效获取数据的数据结构。

B-Tree

为了描述B-Tree，首先定义一条数据记录为一个二元组[key, data]，key为记录的键值，对于不同数据记录，key是互不相同的；data为数据记录除key外的数据。

那么B-Tree是满足下列条件的数据结构：

• d为大于1的一个正整数，称为B-Tree的度。
• h为一个正整数，称为B-Tree的高度。
• 每个非叶子节点由n-1个key和n个指针组成，其中d<=n<=2d。
• 每个叶子节点最少包含一个key和两个指针，最多包含2d-1个key和2d个指针，叶节点的指针均为null 。
• 所有叶节点具有相同的深度，等于树高h。
• key和指针互相间隔，节点两端是指针。
• 一个节点中的key从左到右非递减排列。
• 所有节点组成树结构。
• 每个指针要么为null，要么指向另外一个节点。
• 如果某个指针在节点node最左边且不为null，则其指向节点的所有key小于v(key1)，其中v(key1)为node的第一个key的值。
• 如果某个指针在节点node最右边且不为null，则其指向节点的所有key大于v(keym)，其中v(keym)为node的最后一个key的值。
• 如果某个指针在节点node的左右相邻key分别是keyi和keyi+1且不为null，则其指向节点的所有key小于v(keyi+1)且大于v(keyi)。

B-Tree上查找算法的伪代码如下：

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

B-Tree有许多变种，其中最常见的是B+Tree，例如MySQL就普遍使用B+Tree实现其索引结构。

与B-Tree相比，B+Tree有以下不同点：

• 每个节点的指针上限为2d而不是2d+1。
• 内节点不存储data，只存储key；叶子节点不存储指针。

MyISAM索引实现

MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。
在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。

1.没有对事务的支持
2.不支持行级锁和外键
3.当insert或update即写操作时需要锁定整个表
4.存储了表的行数（所以执行select count 时MyISAM会更快）
5.支持全文类型索引

InnoDB索引实现

虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同。

• 第一个重大区别是InnoDB的数据文件本身就是索引文件。
• 第二个不同是InnoDB的辅助索引data域存储相应记录主键的值，而MyISAM索引存储的是地址。

1.提供了数据库ACID事务的支持
2.实现了SQL的四种隔离级别
3.提供了行级锁和外键约束
4.没有保存表的行数
5.不支持全文索引