网站建设 客户,品牌设计案例分析,找个产品做区域代理,网页设计推荐MySQL中数据是索引组织表#xff0c;即表中数据按照主键顺序存放。所以就可以基于索引这种数据结构实现一些高级算法#xff0c;来提高检索效率。常见的查找算法顺序查找#xff1a;复杂度O(n)#xff0c;在数据量大时#xff0c;效率很低二分查找#xff1a;在有序为前提…MySQL中数据是索引组织表即表中数据按照主键顺序存放。所以就可以基于索引这种数据结构实现一些高级算法来提高检索效率。常见的查找算法顺序查找复杂度O(n)在数据量大时效率很低二分查找在有序为前提复杂度O(logn)hash查找无法满足范围查找二叉树查找O(logn)每个节点只能有一个左节点和一个右节点试着用二叉树来构造一种索引方式为什么MySQL没有采用二叉树来构造索引呢由磁盘的物理结构决定的。首先二叉树中每个节点只能有一个左节点和一个右节点直接导致树的高度很高逻辑上相近的节点无法利用局部性相邻节点没法直接通过指针相连可能需要返回上层节点重复递归找到结果效率低。其次当数据量大时内存不够大部分数据只能存放在磁盘上只有在需要的时候才加载到内存中但是磁盘读取速度显然与内存差很多大部分时间会阻塞在IO上面为了减少磁盘IO次数上面这些传统的树无法满足。磁盘结构—下面是磁盘整体结构示意图其中磁盘可以转动(各个磁盘必须同步转动)。每个磁头负责存取一个磁盘的内容。磁头不能转动但是可以沿磁盘半径方向运动(实际是斜切向运动)。盘片结构示意图盘片被划分成一系列同心环圆心是盘片中心每个同心环叫做一个磁道所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段每个段叫做一个扇区每个扇区是磁盘的最小存储单元。磁盘如何读取数据磁盘如何可以提高IO效率为了提高效率要尽量减少磁盘I/O磁盘往往不是严格按需读取而是每次都会预读即使只需要一个字节磁盘也会从这个位置开始顺序向后读取一定长度的数据放入内存。由于磁盘顺序读取的效率很高(不需要寻道时间只需很少的旋转时间)因此对于具有局部性的程序来说预读可以提高I/O效率。预读的长度一般为页(page)(在许多操作系统中页的大小通常为4k)的整倍数。主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时会触发一个缺页异常此时系统会向磁盘发出读盘信号磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中然后异常返回程序继续运行。为了减少磁盘 IO 次数B-/B树应运而生。B-/B树—B-树为了更快B-树每次将范围分割为多个区间区间越多定位数据越快越精确。所以新建节点时直接申请页大小的空间计算机内存分配是按页对齐的这样就实现了一个节点只需要一次 IO。那么总 IO 的次数就缩减为了 log n 次。下面是一棵简化的B-树B-树的每个节点是 n 个有序的序列(a1,a2,a3…an)并将该节点的子节点分割成 n1 个区间来进行索引(X1 a1, a2 X2 a3, … , an1 Xn anXn1 an)。每个 key 值紧跟着 data 域B-树的 key 和 data 是聚合在一起的。B-树的如何进行查找的比如上图中若搜索 key 为 25 节点的 data首先在根节点进行二分查找(因为 keys 有序二分最快)判断 key 25 小于 key 50所以定位到最左侧的节点此时进行一次磁盘 IO将该节点从磁盘读入内存接着继续进行上述过程直到找到该 key 为止。B树B树是B-树的变种它与B-树的不同之处在于在B树中key 副本存储在内部节点真正的 key 和 data 存储在叶子节点上 。n 个 key 值的节点指针域为 n 而不是 n1。为了增加 区间访问性一般会对B树做一些优化增加了顺序访问指针。下面是一棵简化的B树因为内节点并不存储 data所以一般B树的叶节点和内节点大小不同而B-树的每个节点大小一般是相同的为一页。因为增加了顺序访问指针图中如果要查询key为从55到62的所有数据记录当找到50后只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点极大提到了区间查询效率。B-树与B树区别1.B树内节点不存储数据所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而B-树查询时间复杂度不固定与 key 在树中的位置有关最好为O(1)。如上图如果查找50刚好第一次就可以查找出来所以最好情况是O(1)。由于B树所有的 data 域都在根节点所以查询 key 为 50的节点必须从根节点索引到叶节点时间复杂度固定为 O(log n)。2.B树叶节点两两相连可大大增加区间访问性可使用在范围查询等而B-树每个节点 key 和 data 在一起则无法区间查找。B树可以很好的利用局部性原理若我们访问节点 key为 50则 key 为 55、60、62 的节点将来也可能被访问我们可以利用磁盘预读原理提前将这些数据读入内存减少了磁盘 IO 的次数。当然B树也能够很好的完成范围查询。比如查询 key 值在 50-70 之间的节点。3.B树更适合外部存储。由于内节点无 data 域每个节点能索引的范围更大更精确由于B-树节点内部每个 key 都带着 data 域而B树节点只存储 key 的副本真实的 key 和 data 域都在叶子节点存储。由于磁盘 IO 数据大小是固定的在一次 IO 中单个元素越小量就越大。这就意味着B树单次磁盘 IO 的信息量大于B-树从这点来看B树相对B-树磁盘 IO 次数少。MySQL索引实现—在MySQL中索引属于存储引擎级别的概念不同存储引擎对索引的实现方式是不同的本文主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式。索引分为聚集索引(Primary key)按照每张表的主键构造一棵B树同时叶子节点中存放的即为整张表的行记录数据也将聚集索引的叶子节点称为数据页。每个数据页都通过一个双向链表来进行链接。每张表只能拥有一个聚集索引。辅助索引(Secondary key)叶子节点并不包含行记录的全部数据。叶子节点除了包含键值以外还包含一个书签该书签找到与索引相对应的行数据。每张表可以有多个辅助索引。MyISAM引擎的实现下图是MyISAM索引的原理图在MyISAM中主索引和辅助索引在结构上没有任何区别只是主索引要求key是唯一的而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引则此索引的结构如下图所示InnoDB引擎的实现而在InnoDB中表数据文件本身就是按BTree组织的一个索引结构这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键因此InnoDB表数据文件本身就是主索引。下图是InnoDB主索引示意图可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集所以InnoDB要求表必须有主键(MyISAM可以没有)。下图为定义在Col3上的一个辅助索引这里以英文字符的ASCII码作为比较准则。辅助索引搜索需要检索两遍索引首先检索辅助索引获得主键然后用主键到主索引中检索获得记录。这里就很容易明白为什么不建议使用过长的字段作为主键因为所有辅助索引都引用主索引过长的主索引会令辅助索引变得过大。非单调的主键会造成在插入新记录时数据文件为了维持BTree的特性而频繁的分裂调整十分低效而使用自增字段作为主键则是一个很好的选择。数据的查找—1、精确查找: select * from user_info where id 23内存中找到根节点根节点二分查找确定范围逐层向下查找读取叶子节点通过二分查找找到记录或未命中。2、索引范围查找select * from user_info where id 18 and id 22内存中找到根节点确定索引定位条件id18找到满足条件第一个叶节点顺序扫描所有结果直到终止条件满足id 223、全表扫描select * from user_info where name abc直接读取叶节点头结点 顺序扫描 返回符合条件记录 到最终节点结束4、二级索引查找Select * from table_x where name “d”;id是主索引name是二级索引。通过二级索引查出对应主键拿主键回表查主键索引得到数据 二级索引可筛选掉大量无效记录提高效率。参考文献1、《MySQL技术内幕》
