主存的存取过程如下：
当体系须要攫取主存时，则将地址旌旗灯号放到地址总线上传给主存，主存读到地址旌旗灯号后，解析旌旗灯号并定位到指定存储单位，然后将此存储单位数据放到数据总线上，供其它部件攫取。
写主存的过程类似，体系将要写入单位地址和数据分别放在地址总线和数据总线上，主存攫取两个总线的内容，做响应的写操作。
这里可以看出，主存存取的时光仅与存取次数呈线性关系，因为不存在机械操作，两次存取的数据的“距离”不会对时光有任何影响，例如，先取A0另娶A1和先取A0另娶D3的时光消费是一样的。
上文说过，索引一般以文件情势存储在磁盘上，索引检索须要磁盘I/O操作。与主存不合，磁盘I/O存在机械袈渌动消费，是以磁盘I/O的时光消费是巨大年夜的。
图6是磁盘的┞符体构造示意图。
图6
示例数据库
图11
一个磁盘由大年夜小雷同且同轴的圆形盘片构成，磁盘可以迁移转变(各个磁盘必须同步迁移转变)。在磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负粜ユ取一个磁盘的内容。磁头不克不及迁移转变，然则可以沿磁盘半径偏向活动(实际是斜切向活动)，每个磁头同一时刻也必须是同轴的，即大年夜正上偏向下看，所有磁头任何时刻都是重叠的(不过今朝已经有多磁头自力技巧，可不受此限制)。
图7是磁盘构造的示意图。
图7
盘片被划分成一系列齐心环，圆心是盘片中间，每个齐心环叫做一个磁道，所有半径雷同的磁道构成一个柱面。磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单位。为了简单起见，我们下面假设磁盘只有一个盘片和一个磁头。
当须要大年夜磁盘攫取数据时，体系会将数据逻辑地址传给磁盘，磁盘的┞菲握电路按照寻址逻辑将逻辑地址翻译成物理地址，即肯定要读的数据在哪个磁道，哪个扇区。为了攫取这个扇区的数据，须要将磁头放到这个扇区上方，为了实现这一点，磁头须要移动对准响应磁道，这个过程叫做寻道，所消费时光叫做寻道时光，然后磁回扭转将目标扇区扭转到磁头下，这个过程消费的时光叫做扭转时光。
局部性道理与磁盘预读
因为存储介质的特点，磁盘本身存取就比主存慢很多，再加上机械袈渌动消费，磁盘的存取速度往往是主存的几百分分之一，是以为了进步效力，要尽量削减磁盘I/O。为了达到这个目标，磁盘往往不是严格按需攫取，而是每次都邑预读，即使只须要一个字节，磁盘也会大年夜这个地位开端，次序向后攫取必定长度的数据放入内存。如许做的理论根据是计算机科学中有名的局部性道理：
当一个数据被用到时，其邻近的数据也平日会立时被应用。
法度榜样运行时代所须要的数据平日比较集中。
因为磁盘次序攫取的效力很高(不须要寻道时光，只需很少的扭转时光)，是以对于具有局部性的法度榜样来说，预读可以进步I/O效力。
预读的长度一般为页(page)的┞符倍数。页是计算机治理存储器的逻辑块，硬件及操作体系往往将主存和磁盘存储区瓜分为持续的大年夜小相等的块，每个存储块称为一页(在很多操作体系中，页得大年夜小平日为4k)，主存和磁盘以页为单位交换数据。当法度榜样要攫取的数据不在主存中时，会触发一个缺页异常，此时体系挥蒡磁盘发出读盘旌旗灯号，磁盘会找到数据的肇端地位并向后持续攫取一页或几页载入内存中，然后异常返回，法度榜样持续运行。
磁盘存取道理
上文说过一般应用磁盘I/O次数评价索引构造的好坏。先大年夜B-Tree分析，根据B-Tree的定义，可知检索一次最多须要拜访h个节点。数据库体系的设计者奇妙应用了磁盘预读道理，将一个节点的大年夜小设为等于一个页，如许每个节点只须要一次I/O就可以完全载入。为了达到这个目标，在实际实现B-Tree还须要应用如下技能：
每次新建节点时，直接申请一个页的空间，如许就包管一个节点物理上也存储在一个页里，加之计算机存储分派都是按页对齐的，就实现了一个node只需一次I/O。
B-Tree一一次检索最多须要h-1次I/O(根节点常驻内存)，渐进复杂度为O(h)=O(logdN)。一般实际应用中，出度d是异常大年夜的数字，平日跨越100，是以h异常小(平日不跨越3)。
综上所述，用B-Tree作为索引构造效力是异常高的。
而红黑树这种构造，h明显要深的多。因为逻辑上很近的节点(父子)物理上可能很远，无法应用局部性，所以红黑树的I/O渐进复杂度也为O(h)，效力明显比B-Tree差很多。
上文还说过，B+Tree更合适外存索引，原因和内节点出度d有关。大年夜膳绫擎分析可以看到，d越大年夜索引的机能越好，而出度的上限取决于节点内key和data的大年夜小：
dmax = floor(pagesize / (keysize + datasize + pointsize)) (pagesize – dmax >= pointsize)
或
dmax = floor(pagesize / (keysize + datasize + pointsize)) – 1 (pagesize – dmax < pointsize)
floor表示向下取整。因为B+Tree内节点去掉落了data域，是以可以拥有更大年夜的出度，拥有更好的机能。
这一章大年夜理论角度评论辩论了与索引相干的数据构造与算法问题，下一章将评论辩论B+Tree是若何具体实现为MySQL中索引，同时将结合MyISAM和InnDB存储引擎介绍非集合索引和集合索引两种不合的索引实现情势。
MySQL索引实现
在MySQL中，索引属于存储引擎级其余概念，不合存储引擎对索引的实现方法是不合的，本文重要评论辩论MyISAM和InnoDB两个存储引擎的索引实现方法。
MyISAM索引实现
MyISAM引擎应用B+Tree作为索引构造，叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的道理图：
推荐阅读
【51CTO.com原创稿件】前不久，华为与石化盈科隆重推出了两边深度合作后首个重要>>>详细阅读
本文标题：MySQL：数据结构及算法原理
地址：http://www.17bianji.com/lsqh/35159.html
1/2 1
网友点评
精彩导读
科技快报
品牌展示