6-2 剖析MySQL数据结构的恰当选取

3周前发布 gsjqwyl

11 0 0

6-2 探讨MySQL数据结构的合理选用

查找通常是索引操作，一般而言索引规模较大，特别是关系型数据库，当数据量较多时，索引的大小有可能达到几个G甚至更多，为了减少索引在内存中的占用，数据库索引是存储在外部磁盘上的。当我们借助索引进行查询时，不可能把整个索引全部加载到内存，只能逐一加载，所以MySQL衡量查询效率的标准就是磁盘的IO次数。

1. 全表查询

全表查询相对比较简易，此处就不再详细展开阐述了。

2. Hash查询

用于加快查找速度的数据结构，常见有两类：一是树，比如平衡二叉搜索树，其查询、插入、修改、删除的平均时间复杂度均为O(log₂N)；二是哈希，比如HashMap，其查询、插入、修改、删除的平均时间复杂度均为O(1)，形式为(key, value)。图中的哈希函数h有可能把两个不同的关键字映射到同一个位置，这被称作碰撞，在数据库里通常采用链接法来解决。在链接法中，把散列到同一槽位的元素放在一个链表中，就像下图所示。

实验：体会数组和hash表的查找方面的效率区别

// 算法复杂度为 O(n)
@Test
public void test1(){
    int[] arr = new int[100000];
    for(int i = 0;i < arr.length;i++){
        arr[i] = i + 1;
    }
    long start = System.currentTimeMillis();
    for(int j = 1; j<=100000;j++){
        int temp = j;
        for(int i = 0;i < arr.length;i++){
            if(temp == arr[i]){
                break;
            }
        }
    }
    long end = System.currentTimeMillis();
    System.out.println("time： " + (end - start)); //time： 823
}

// 算法复杂度为 O(1)
@Test
public void test2(){
    HashSet<Integer> set = new HashSet<>(100000);
    for(int i = 0;i < 100000;i++){
        set.add(i + 1);
    }
    long start = System.currentTimeMillis();
    for(int j = 1; j<=100000;j++) {
        int temp = j;
        boolean contains = set.contains(temp);
    }
    long end = System.currentTimeMillis();
    System.out.println("time： " + (end - start)); //time： 5
}

Hash结构效率高，那为什么索引结构要设计成树型呢？

Hash索引适用存储引擎如表所示：

索引 / 存储引擎	MyISAM	InnoDB	Memory
HASH索引	不支持	不支持	支持

Hash索引的适用性：

采用自适应 Hash 索引目的是方便根据 SQL 的查询条件加速定位到叶子节点，特别是当 B+ 树比较深的时候，通过自适应 Hash 索引可以明显提高数据的检索效率。

我们可以通过 innodb_adaptive_hash_index 变量来查看是否开启了自适应 Hash，比如：

mysql> show variables like '%adaptive_hash_index';

3. 二叉搜索树

若把二叉树当作索引结构来使用，那么磁盘的IO次数和索引树的高度是有关系的。

1. 二叉搜索树的特点

一个节点最多只能有两个子节点，也就是一个节点的度不能超过2
左子节点的值小于本节点的值；右子节点的值大于等于本节点的值，比本节点大的往右边走，比本节点小的往左边走

2. 查找规则

为了提高查询效率，就需要减少磁盘IO数。要减少磁盘IO的次数，就需要尽量降低树的高度，得把原来“瘦高”的树结构变得“矮胖”，树的每层分叉越多越好。

4. AVL树

每次访问一个节点都得进行一次磁盘I/O操作，针对上面那棵树而言，我们需要进行5次I/O操作。虽说平衡二叉树效率高，但树的深度也不小，这就意味着磁盘I/O操作次数多，会对整体的数据查询效率产生影响。

针对同样的数据，如果把二叉树改成M叉树（M>2）呢？当M=3时，同样的31个节点可以由下面的三叉树来进行存储：

能看到此时树的高度降低了，当数据量N大的时候，以及树的分叉数M大的时候，M叉树的高度会远小于二叉树的高度 (M > 2)。所以，我们需要把树从“瘦高”变“矮胖”。

5. B-Tree

B树的英文是Balance Tree，也就是多路平衡查找树，简称为B-Tree。它的高度比平衡二叉树低很多。

一个M阶的B树（M>2）有如下特性：
1. 根节点的子节点数量范围是[2,M]。
2. 每个中间节点包含k-1个关键字和k个孩子，孩子数量等于关键字数量加1，k的取值范围是[ceil(M/2), M]。
3. 叶子节点包含k-1个关键字（叶子节点没有孩子），k的取值范围是[ceil(M/2), M]。
4. 假设中间节点的关键字为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]的子树。
5. 所有叶子节点处于同一层。

上面那张图所表示的B树就是一棵3阶的B树。看磁盘块2，里面的关键字是（8，12），它有3个孩子(3，5)，(9，10)和(13，15)，能看到(3，5)小于8，(9，10)在8和12之间，而(13，15)大于12，正好符合刚才给出的特征。

然后来看如何用B树进行查找。假设想要查找的关键字是9，步骤如下：
1. 与根节点的关键字(17，35）进行比较，9小于17那么得到指针P1；
2. 按照指针P1找到磁盘块2，关键字为（8，12），因为9在8和12之间，所以得到指针P2；
3. 按照指针P2找到磁盘块6，关键字为（9，10），然后找到了关键字9。

能看出来在B树的搜索过程中，比较的次数并不少，但如果把数据读取出来然后在内存中进行比较，这个时间就可以忽略不计。而读取磁盘块本身需要进行I/O操作，消耗的时间比在内存中进行比较所需要的时间要多，是数据查找用时的重要因素。B树相比于平衡二叉树来说磁盘I/O操作要少，在数据查询中比平衡二叉树效率要高。所以只要树的高度足够低，IO次数足够少，就可以提高查询性能。

再举例1：

6.B + Tree

B+树也是一种多路搜索树，是在B树基础上进行改进的，主流的DBMS都支持B+树的索引方式，像MySQL，相比于B-Tree，B+Tree适合文件索引系统。

MySQL官网说明：

B+树和B树的差别体现在以下几点：
1. 有k个孩子的节点就有k个关键字，也就是孩子数量等于关键字数，而B树中孩子数量等于关键字数加1。
2. 非叶子节点的关键字也会同时出现在子节点中，并且是子节点中所有关键字的最大（或最小）。
3. 非叶子节点仅用于索引，不存储数据记录，和记录有关的信息都放在叶子节点中，而B树中非叶子节点既存索引又存数据记录。
4. 所有关键字都在叶子节点出现，叶子节点构成一个有序链表，而且叶子节点本身按照关键字的大小从小到大依次链接。

B树和B+树都能作为索引的数据结构，在MySQL中采用的是B+树，不过B树和B+树各有其应用场景，不能说B+树完全比B树好，反过来也一样。

思考题：为了减少IO，索引树会一次性加载吗？

思考题：B+树的存储能力如何？为何说一般查找行记录，最多只需1~3次磁盘IO

思考题：为什么说B+树比B-树更适合实际应用中操作系统的文件索引和数据库索引？

思考题：Hash 索引与 B+ 树索引的区别

思考题：Hash 索引与 B+ 树索引是在建索引的时候手动指定的吗？

7. 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的优势在于范围查找。

索引 / 存储引擎	MyISAM	InnoDB	Memory
R-Tree索引	支持	支持	不支持

8. 小结

使用索引能够帮助我们从大量的数据中快速找到想要查找的数据，不过索引也存在一些不足之处，比如占用存储空间、降低数据库写操作的性能等，如果有多个索引还会增加索引选择的时间。当我们使用索引时，需要权衡索引的利（提升查询效率）和弊（维护索引所需的代价）。在实际工作中，我们还得依据实际的需求以及数据本身的分布情况来决定是否使用索引，尽管索引不是万能的，但数据量大的时候不使用索引是难以想象的，毕竟索引的本质就是帮助我们提升数据检索的效率。