数据结构与索引-- mysql InnoDB存储引擎索引

本是古典何须时尚 2023-01-13 01:41 121阅读 0赞

#### 索引与算法 ####

*  索引是我们在应用开发过程中程序数据可开发的一个重要助力。也是一个重要的研究方向，索引太多，应用的性能可能受到影响，如果索引太少，对查询性能又会有制约。我们需要找到一个合适的平衡点，这个对性能至关重要。
 *  一种错误的开发模式在于：总数在事后才想起来添加索引，我一直认为我们应该在数据库设计时候，先预估此数据库承载的业务查询有哪些，在清楚了查询的具体用法后，依据我们需要的查询在建表的时候建立合适的索引。
 *  或者认为业务上线后让DBA加上索引。但是DBA往往是不了解业务的数据流，添加索引需要通过监控大量SQL语句，从中找到问题。在添加索引解决问题，这是一个漫长的过程，也许此时业务已经是非正常状态了
 *  当然索引并不是越多越好，看一个实际业务中遇到的案例：
    
     *  有如下一张表：

CREATE TABLE `MemberViewRecommend_000` (
    `id` int(11) NOT NULL AUTO_INCREMENT,
    `memberId` int(11) NOT NULL,
    `viewerID` int(11) NOT NULL COMMENT '查看用户id',
    `objectID` int(11) NOT NULL COMMENT '被查看用户id',
    `viewDate` datetime NOT NULL COMMENT '最后一次查询时间',
    `isDeclared` smallint(6) DEFAULT '0' COMMENT '是否表态 0-未表态 1-已表态',
    `isGreeted` smallint(6) DEFAULT '0' COMMENT '是否打招呼过 0-未打招呼 1-已打招呼',
    `viewCount` int(11) NOT NULL DEFAULT '0' COMMENT '访问总次数',
    `hasDefaultPhoto` smallint(6) NOT NULL DEFAULT '0' COMMENT '是否有头像信息 0-无头像 1-有头像',
    `isShield` tinyint(4) unsigned NOT NULL DEFAULT '0' COMMENT '是否屏蔽 0-未屏蔽 1-已屏蔽',
    `createTime` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '创建时间',
    `updateTime` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '更新时间',
    PRIMARY KEY (`id`),
    KEY `ViewDate` (`viewDate`),
    KEY `IsGreeted` (`isGreeted`),
    KEY `HasDefaultPhoto` (`hasDefaultPhoto`),
    KEY `memberId` (`memberId`),
    KEY `objectID` (`objectID`),
    KEY `viewerID` (`viewerID`)
    ) ENGINE = InnoDB AUTO_INCREMENT = 3757292 DEFAULT CHARSET = utf8mb4 COMMENT = '谁看过我推荐表'

*  刚上线时候的建表语句，业务初期是无异常情况的，当数据量查询出现偶尔的超时，而且这台mysqliostat显示磁盘使用率95%
 *  以上表承建立的索引比较多，因为承载的业务查询主要是三个：
    
     *  第一：`memberId`,`isDeclared`,`isShield`,`isGreeted`,`viewDate` 字段的查询
     *  第二：`memberId`, `objectID`, `viewerID` 字段查询
     *  第三：`memberId`, `viewerID` 字段的查询
 *  因为我们建立的都是单个索引，每个索引都会有自己的BTree，经过优化后，得到如下索引：

CREATE TABLE `MemberViewRecommend_000` (
    `id` int(11) NOT NULL AUTO_INCREMENT,
    `memberId` int(11) NOT NULL,
    `viewerID` int(11) NOT NULL COMMENT '查看用户id',
    `objectID` int(11) NOT NULL COMMENT '被查看用户id',
    `viewDate` datetime NOT NULL COMMENT '最后一次查询时间',
    `isDeclared` smallint(6) DEFAULT '0' COMMENT '是否表态 0-未表态 1-已表态',
    `isGreeted` smallint(6) DEFAULT '0' COMMENT '是否打招呼过 0-未打招呼 1-已打招呼',
    `viewCount` int(11) NOT NULL DEFAULT '0' COMMENT '访问总次数',
    `hasDefaultPhoto` smallint(6) NOT NULL DEFAULT '0' COMMENT '是否有头像信息 0-无头像 1-有头像',
    `isShield` tinyint(4) unsigned NOT NULL DEFAULT '0' COMMENT '是否屏蔽 0-未屏蔽 1-已屏蔽',
    `createTime` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '创建时间',
    `updateTime` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '更新时间',
    PRIMARY KEY (`id`),
    KEY `ViewDate` (`viewDate`),
    KEY `idx_mid_id_is_vd` (
    `memberId`,
    `isDeclared`,
    `isShield`,
    `isGreeted`,
    `viewDate`
    ),
    KEY `idx_mid_oid_vid` (`memberId`, `objectID`, `viewerID`),
    KEY `idx_mid_vid` (`memberId`, `viewerID`)
    ) ENGINE = InnoDB AUTO_INCREMENT = 3757292 DEFAULT CHARSET = utf8mb4 COMMENT = '谁看过我推荐表'

*  在删除一些索引，并且加上特定查询的符合索引后，磁盘利用率下降为40%左右，因此索引的添加也是有一定技巧的。

#### InnoDB存储引擎索引 ####

*  InnoDB存储引擎支持两种常见的索引，一种是B+树索引，另一种哈希索引。
    
     *  Innodb存储引擎支持的哈希索引是自适应的，InnoDB存储引擎会根据表的使用情况自动为表生成哈希索引，不能认为干预表中生成哈希索引
     *  B+树索引就是传统意义上的索引，这是目前关系型数据库中常用的，最有效的索引。B+树索引的构造类似二叉树，更具键值key，value，快速找到数据。
 *  此处B+ 树中的B并不代表二叉（binary），而是代表平衡（balance），因为B+ 树是从最早的平衡二叉树演化而来，但是B+ 树不是二叉树
 *  InnoDB中B+树索引并不能找到一个给定键值的具体行。B+树索引能找到的只是被查找数据行所在的页。然后数据库通过吧页读入内存，在内存中进行查找，最后得到查找的数据。

#### 算法相关 ####

*  InnoDB中B+ 树作为索引是一步一步演化过程，接下来我们以此来讲解相关算法的演化过程。其中有一些是之前章节详细分析过，我会直接引用对应的文章。

##### 二分查找 #####

*  二分查找（binary search）也称为折半查找方法，用来查找一组有序的记录数组中的某一个记录。基本思想如下：
    
     *  降级了有序化（升序，降序都行）排列，
     *  查询过程采用跳跃式查找，先查中点位置对象
     *  中点位置小于目标值，则查后半部分数据（升序情况）
     *  中的位置大于目标值，则查前半部分数据（升序情况）
     *  讲需要重新查找的半部分依据以上步骤继续执行，得到最终结果
     *  例如：5,10,19,21,31,37,42,48,50,52这10个数据查找48 ，查找过程如下

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYW9qaWFtaW4wMTAy_size_16_color_FFFFFF_t_70]

*  如上图，用3次就能找到48 这个数，依据如上分析有如下代码：

/** * 递归实现二分查找 * @author liaojiamin * @Date:Created in 15:43 2021/4/13 */
    public class BinarySearch { 
        public static int binarySearchNum(int[] array, int target){ 
            return binarySearchNum(array, target, 0, array.length -1);
        }
    
        public static int binarySearchNum(int[] array, int target, int left, int right){ 
            if(array == null){ 
                return -1;
            }
            if(left < 0 || right > array.length-1){ 
                return -1;
            }
            if(left > right){ 
                return -1;
            }
            int middle = (left + right)/2;
            if(array[middle] == target){ 
                return middle;
            }
            if(array[middle] > target){ 
                return binarySearchNum(array, target, left, middle-1);
            }
            if(array[middle] < target){ 
                return binarySearchNum(array, target, middle+1, right);
            }
            return -1;
        }
    
        public static void main(String[] args) { 
            int[] array = { 5,10,19,21,31,37,42,48,50,52};
            System.out.println(binarySearchNum(array, 89));
        }
    }

*  如上案例中，如果顺序查找需要8 次，因此二分查找的效率更高。当如果查询5 这条记录，顺序查找只需要1次，二分查找需要4次。对应以上10个数字，顺序查找的平均此时为（1+2+3+…+10 ）/10 = 5.5次，二分查找（4,+3+2+4+3+1+4+3+2+3）/10 = 2.9次，最坏情况，顺序查询10次，二分查找4次。
 *  二分查找的思想应用极其广泛，思想易于理解，第一个二分查找是1946年出现，而mysql存储的数据也PageDirectory的槽就是按照主键的顺序存放，对于某一条具体记录查询是通过对Page Directory进行二分查找得到的。

##### B+树对应数据结构演化过程 #####

*  在介绍B+树之前我们需要了解一下二叉树，二叉查找树等这些数据结构。应为B+ 树是通过二叉树，二叉查找树，再有平衡二叉树,B树演化过来的。读个之前章节的朋友可以找到每一个对应的章节，此处我只做解释以及应用，不在详细展开讲解。
 *  二叉树见详细文章，[数据结构与算法–二叉树实现原理][Link 1]
 *  二叉查找树是有一定特点的二叉树，每个节点的键值左子树的键值总比根键值小，右子树的键值总比根节点大，详细分析：[数据结构与算法–二叉查找树实现原理][Link 2].
 *  B树是在二叉查找树的技术上改动，更加有利于磁盘的读写，详见：[数据结构与算法–B树原理及实现][B]
 *  B+ 树和二叉树，平衡二叉树，B树，都是经典的数据结构。B+树有B树和索引顺序范问方法ISAM（也就是MyISAM引擎最初参考的数据结构）演化而来，时间使用过程中几乎已经没有使用B树的情况了。
 *  B+树定义与B树类似，只是在每一个层级的节点之间有指针链接，并且首尾节点有指针链接，类似双向链表，如下图：
 *  我们还是用 数据结构与算法–B树原理及实现 一节中B树的案例进行修改，展示B+ 树的结构如下：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYW9qaWFtaW4wMTAy_size_16_color_FFFFFF_t_70 1]
 *  如上，只画出了第二层节点中的指针，底层叶子节点也是一样的效果，如上B+树，高度为3，每页可以存放4条记录，扇出为5（叶子节点中有五个键值），所有叶子节点中都是顺序存放，如果我们从左到右的叶子节点顺序范问遍历，可以得到所有键值的顺序排序：2,4，6,8，10,12,14,16，…92，93,95,97,98
 *  B+树的插入，删除 节点操作与B树的原理是一致的详细参考：[数据结构与算法–B树原理及实现][B]
 *  至此关于B+ 树索引的算法与数据结构部分算讲完，其实算是之前文章的总结。接下来我将详细的讲解一下B+数索引，已经B+shu索引的使用。

[上一篇：MySql 内连接，外连接查询方式区别][MySql]  
[下一篇：数据结构与索引-- B+树索引][-- B]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYW9qaWFtaW4wMTAy_size_16_color_FFFFFF_t_70]: /images/20221022/04f9d044456d4887872e052bbc77ee36.png
[Link 1]: https://blog.csdn.net/liaojiamin0102/article/details/111043418
[Link 2]: https://blog.csdn.net/liaojiamin0102/article/details/111231303
[B]: https://blog.csdn.net/liaojiamin0102/article/details/111375342
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYW9qaWFtaW4wMTAy_size_16_color_FFFFFF_t_70 1]: /images/20221022/8ac38b25ecc54a78bf48ce8e9b70d110.png
[MySql]: https://blog.csdn.net/liaojiamin0102/article/details/94462596
[-- B]: https://blog.csdn.net/liaojiamin0102/article/details/115724427