数据结构与索引-- mysql InnoDB存储引擎索引
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构与索引-- mysql InnoDB存储引擎索引，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7368字，纯文字阅读大概需要11分钟。
内容图文
索引与算法
- 索引是我们在应用开发过程中程序数据可开发的一个重要助力。也是一个重要的研究方向，索引太多，应用的性能可能受到影响，如果索引太少，对查询性能又会有制约。我们需要找到一个合适的平衡点，这个对性能至关重要。
- 一种错误的开发模式在于：总数在事后才想起来添加索引，我一直认为我们应该在数据库设计时候，先预估此数据库承载的业务查询有哪些，在清楚了查询的具体用法后，依据我们需要的查询在建表的时候建立合适的索引。
- 或者认为业务上线后让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 ，查找过程如下
- 如上图，用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树演化过来的。读个之前章节的朋友可以找到每一个对应的章节，此处我只做解释以及应用，不在详细展开讲解。
-
二叉树见详细文章，数据结构与算法–二叉树实现原理
-
二叉查找树是有一定特点的二叉树，每个节点的键值左子树的键值总比根键值小，右子树的键值总比根节点大，详细分析：数据结构与算法–二叉查找树实现原理.
-
B树是在二叉查找树的技术上改动，更加有利于磁盘的读写，详见：数据结构与算法–B树原理及实现
-
B+ 树和二叉树，平衡二叉树，B树，都是经典的数据结构。B+树有B树和索引顺序范问方法ISAM（也就是MyISAM引擎最初参考的数据结构）演化而来，时间使用过程中几乎已经没有使用B树的情况了。
-
B+树定义与B树类似，只是在每一个层级的节点之间有指针链接，并且首尾节点有指针链接，类似双向链表，如下图：
-
我们还是用 数据结构与算法–B树原理及实现 一节中B树的案例进行修改，展示B+ 树的结构如下：
-
如上，只画出了第二层节点中的指针，底层叶子节点也是一样的效果，如上B+树，高度为3，每页可以存放4条记录，扇出为5（叶子节点中有五个键值），所有叶子节点中都是顺序存放，如果我们从左到右的叶子节点顺序范问遍历，可以得到所有键值的顺序排序：2,4，6,8，10,12,14,16，…92，93,95,97,98
-
B+树的插入，删除 节点操作与B树的原理是一致的详细参考：数据结构与算法–B树原理及实现
-
至此关于B+ 树索引的算法与数据结构部分算讲完，其实算是之前文章的总结。接下来我将详细的讲解一下B+数索引，已经B+shu索引的使用。
内容总结
以上是互联网集市为您收集整理的数据结构与索引-- mysql InnoDB存储引擎索引全部内容，希望文章能够帮你解决数据结构与索引-- mysql InnoDB存储引擎索引所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。