索引与算法
索引是我们在应用开发过程中程序数据可开发的一个重要助力。也是一个重要的研究方向,索引太多,应用的性能可能受到影响,如果索引太少,对查询性能又会有制约。我们需要找到一个合适的平衡点,这个对性能至关重要。一种错误的开发模式在于:总数在事后才想起来添加索引,我一直认为我们应该在数据库设计时候,先预估此数据库承载的业务查询有哪些,在清楚了查询的具体用法后,依据我们需要的查询在建表的时候建立合适的索引。或者认为业务上线后让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 /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 内连接,外连接查询方式区别
下一篇:数据结构与索引-- B+树索引