高性能mysql读书笔记(一) 创建高性能索引_语落心生的专栏文章_微信文章

在mysql中,存储引擎用类似的方法使用索引，其先在索引中找到对应值，然后根据匹配的索引记录找到对应的数据行，加入需要运行下面的查询：

mysql>select first_name form salika.actor where actor_id = 5 如果在actor_id列上建有索引，则mysql将使用索引找到actor_id为5的行,就是说，mysql现在索引列上按值进行查找，然后返回所有的数据行。

索引可以包含一个或者多个列的值。如果索引包含多个列，那么列的顺序十分重要,为mysql只有高效使用索引的最左前缀列。创建一个人包含两个列的索引，和创建两个只包含一列的索引是不大相同的。

mysql索引类型的优点和缺点

B-tree索引 b-tree意味着所有值都是按照顺序存储的，并且每一个叶子页到根的距离相同。
这种索引之所以能够加快访问数据的速度，因为存储引擎不再需要进行全表扫描获取需要的数据，却而代之的是从索引的根节点开始进行搜索。根节点的数据结构中存放了指向子节点的指针如文中所示数据结构

class BTreeNode 
{ 
    int *keys;  // An array of keys 
    int t;      // Minimum degree (defines the range for number of keys) 
    BTreeNode **C; // An array of child pointers 
    int n;     // Current number of keys 
    bool leaf; //Is true when node is leaf. Otherwise false 
}
复制代码

存储引擎根据这些指向孩子的指针往下层查找，通过比较节点页(mysql的最小存储单位，由大到小划分为:表段区页)的值和要查找的值可以找到合适的指针进入下层子节点，这些指针实际上定义了子节点页中值的位置。最终存储引擎要么找到值，要么该记录不存在。叶子结点比较特别，他们的指针指向的是被索引的数据，而不是其他的数据页。在根节点和叶子结点之间可能存在很多的节点页。树的深度和表的大小相关。

B-tree对索引列是按照顺序存储的，即按照索引定义顺序查找的每一条路径。所以很适合查找范围数据。例如在一个基于文本域的索引树上，按照字母传递连续的值进行查找是非常合适的，例如找出所有1到k开头的名字。

假设有以下数据表

create table people(
    last_name varchar(50) not null,
    first_name varchar(50) not null
    dob date not null,
    key(last_name,first_name.dob)
);
复制代码

对于表中每一行的数据。索引中包含了last_name,first_name,dob列的值

B-tree索引适用于全键值，键值范围或者键前缀查找。其中键前缀查找只适用于根据最左前缀查找

关于b-tree的限制：

如果不是按照索引的最左列开始查找，则无法使用索引。
不能跳过索引中的列
如果查询某个列的范围查询，则其右边的所有列都无法使用索引优化查询

hash索引

hash索引基于hash表实现，只有精确匹配索引的所有列的查询才有效，于每一行数据，存储引擎都会对所有的索引列计算一个hash码，hash码有一个较小的值。目前仅支持memory引擎。

先来看看基于hash表的直接索引。当关键字的全域U比较小时候，假设某应用要用到一个动态集合，其中每一个元素都有一个取自全域U={0,1...,m-1}的关键字，同时假设没有两个元素具有相同关键字。

用一个数组T[0..m-1]表示动态集合，其中每个位置对应全域U中的一个关键字。

k指向了集合中一个关键字为k的元素，如果该集合中没有关键字为k的元素，则T[k]=null

但直接寻址存在一个很明显的问题，如果域U很大，在一台计算机的容量下，存储大小为U的一张表不符合实际。所以hash表出现了，该元素出于h(k)中，即利用hash函数h根据关键字k计算出地址的位置。函数h将关键字域U映射带hash表T[0..m-1]的地址位上。

hash表技术很好地解决了直接寻址遇到的问题，但有种情况，两个关键字可能映射到同一个地址位上。这就是在hashmap中解决碰撞的方式散列表的由来。

而对于Innodb存储引擎而言，hash函数采用除法散列方式，对于缓冲池中的page页都有一个chain指针，他指向相同hash数值的页。面向除法散列而言，m的取值为略大于2倍缓冲池页数量的质数，例如：

当前参数innodb_buffer_pool_size的大小为10M，则共有640个16kb的页。对于缓冲池内存的hash表来说，需要分配640*2个地址位。但由于640*2不是质数，需要取比640*2略大一些的质数，所以在启动的时候会分配1399个槽。

Innodb存储引擎的缓冲池对其中的页查找方式如下：

Innodb存储引擎的表空间有一个space_id,用户要查询的应该是某个表空间里某个连续的16KB的页，即偏移量offset。Innodb存储引擎将space_id左移20位，然后加上space_id和offset，即关键字K=space_id<20+space_id+offset。之后除法散列到各个地址位中

hash索引的局限性
- hash索引质保函hash值和行指针，而不存储字段值，所以不能使用索引里面的值来避免读取行
- hash索引数据并不是按照索引值顺序存储的，所以无法用于排序
- hash索引也不支持部分索引列匹配查找，因为hash索引始终是使用索引列的全部内容计算hash值的