数据库B+树ppt

B+树的索引CONTENTSNeverputoffwhatyoucandotodayuntiltomorrowB+树索引结构对B+树索引的整体结构进行讲解B+树索引管理机制对B+树查询和更新操作进行讲解B+树索引实现方式对B+树的文件组织进行描述B+树的比较分析对B+树进行比较分析1B+树索引结构对B+树索引的整体结构进行讲解Youcannotimproveyourpast,butyoucanimproveyourfuture.Oncetimeiswasted,lifeiswasted.B+树索引结构从物理上说，索引通常可以分为：分区和非分区索引、常规B树索引、位图（bitmap）索引、翻转（reverse）索引等。其中，B树索引属于最常见的索引B树索引是一个典型的树结构，其包含的组件主要是：叶子节点（Leafnode）：包含条目直接指向表里的数据行。分支节点（Branchnode）：包含的条目指向索引里其他的分支节点或者是叶子节点。根节点（Rootnode）：一个B树索引只有一个根节点，它实际就是位于树的最顶端分支节点。Formanismanandmasterofhisfate.B+树索引结构所有的叶子结点中包含了全部关键码的信息，及指向含有这些关键码记录的指针，且叶子结点本身依关键码的大小自小而大的顺序链接。所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键码。B+树的特性有n棵子树的结点中含有n个关键码B+树索引结构如果能实现删除算法，则除根节点外，每一个节点都将保证最小50%的占有率。但是，删除的实现通常是简单的定位数据项，并移走它，而不为保证50%的占有率而调整它，这主要是因为文件在典型情况下是增长而不是缩小。搜索记录需要从根开始遍历到合适的叶子。从根到叶子的路径长度称为树的高度，因为是平衡树，所以从根到任意叶子的长度都是相同的。B+树的特性树上的操作（插入，删除）能保持数的平衡B+树索引结构Formanismanandmasterofhisfate..P1K1P2K2……Kn-1Pn对一a=1,2,…n，指针Pi只指向具有搜索码值Ki的一个文件记录或指向一个指针桶，桶中的每个指针指向具有搜索码值Ki的一个文件记录，指针桶只在搜索码不是主码且文件不按搜索码顺序存放时才使用。因为各叶结点之间按照所含的搜索码值大小有一个线性的顺序，我们就用Pn将叶结点按搜索码顺序串在一起。这种排序使我们能够高效地对文件进行顺序处理。这就是指针Pn有特殊的作用LeafNodeB+树的结点结构B+树索引结构Formanismanandmasterofhisfate.K1K2K3InteriorNodeB+树的非叶结点形成叶结点上的一个多级(稀疏)索引。非叶结点的结构和叶结点和同，只不过非叶结点中的所有指针都指向树中的结点。一个非叶结点至少包含[n/2]个指针，最多n个。结点的指针数称为该结点的扇出。B+树的结点结构B+树索引结构Formanismanandmasterofhisfate.509020506080901216202630505560627080828690内部结点只存储搜索码终端结点存储记录引导查找rootsqtB+树简单示例B+树索引结构Formanismanandmasterofhisfate.B+树索引的访问随机访问我们已经知道了B树索引的体系结构，那么当Oracle需要访问索引里的某个索引条目时，Oracle是如何找到该索引条目所在的数据块的呢？当oracle进程需要访问数据文件里的数据块时，oracle会有两种类型的I/O操作方式：顺序访问每次读取一个数据块（通过等待事件“dbfilesequentialread”体现出来）。每次读取多个数据块（通过等待事件“dbfilescatteredread”体现出来）。B+树索引结构Formanismanandmasterofhisfate.B+树索引的访问第一种方式则是访问索引里的数据块，而第二种方式的I/O操作属于全表扫描。这里顺带有一个问题，为何随机访问会对应到dbfilesequentialread等待事件，而顺序访问则会对应到dbfilescatteredread等待事件呢？这似乎反过来了，随机访问才应该是分散（scattered）的，而顺序访问才应该是顺序（sequential）的。其实，等待事件主要根据实际获取物理I/O块的方式来命名的，而不是根据其在I/O子系统的逻辑方式来命名的。下面对于如何获取索引数据块的方式中会对此进行说明。B+树索引结构Formanismanandmasterofhisfate.B+树索引的访问当oracle需要获得一个索引块时，首先从根节点开始，根据所要查找的键值，从而知道其所在的下一层的分支节点，然后访问下一层的分支节点，再次同样根据键值访问再下一层的分支节点，如此这般，最终访问到最底层的叶子节点。可以看出，其获得物理I/O块时，是一个接着一个，按照顺序，串行进行的。在获得最终物理块的过程中，我们不能同时读取多个块，因为我们在没有获得当前块的时候是不知道接下来应该访问哪个块的。因此，在索引上访问数据块时，会对应到dbfilesequentialread等待事件，其根源在于我们是按照顺序从一个索引块跳到另一个索引块，从而找到最终的索引块的。B+树索引结构Formanismanandmasterofhisfate.B+树索引的访问那么对于全表扫描来说，则不存在访问下一个块之前需要先访问上一个块的情况。全表扫描时，oracle知道要访问所有的数据块，因此唯一的问题就是尽可能高效的访问这些数据块。因此，这时oracle可以采用同步的方式，分几批，同时获取多个数据块。这几批的数据块在物理上可能是分散在表里的，因此其对应到dbfilescatteredread等待事件。B+树索引结构Formanismanandmasterofhisfate.B+树功能A快速的Record查找B快速的Record遍历C不通过overflowpage的形式维护排序树结构2B+树索引管理机制Actionspeaklouderthanwords.Youcannotimproveyourpast,butyoucanimproveyourfuture.Oncetimeiswasted,lifeiswasted.B+树索引管理机制Formanismanandmasterofhisfate.B+树索引的查找管理对B+树可以进行两种查找运算：1.从最小关键字起；2.从根结点开始，进行随机查找。在查找时，若非终端结点上的关键值等于给定值，并不终止，而是继续向下直到叶子结点。因此，在B+树中，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。其余同B-树的查找类似。B+树索引管理机制Formanismanandmasterofhisfate.第一种情况第二种情况一种是在一个已经充满了数据的表上创建索引时，索引是怎么管理的。当在一个充满了数据的表上创建索引（createindex命令）时，Oracle会先扫描表里的数据并对其进行排序，然后生成叶子节点。生成所有的叶子节点以后，根据叶子节点的数量生成若干层级的分支节点，最后生成根节点。这个过程是很清晰的。B+树索引的插入管理另一种则是当一行接着一行向表里插入或更新或删除数据时，索引是怎么管理的。当一开始在一个空的表上创建索引的时候，该索引没有根节点，只有一个叶子节点。随着数据不断被插入表里，该叶子节点中的索引条目也不断增加，当该叶子节点充满了索引条目而不能再放下新的索引条目时，该索引就必须扩张，必须再获取一个可用的叶子节点。这时，索引就包含了两个叶子节点，但是两个叶子节点不可能单独存在的，这时它们两必须有一个上级的分支节点，其实这也就是根节点了。B+树索引管理机制Formanismanandmasterofhisfate.599772976372859197rootsqt3阶B+树插入简单示例154459101521374451599插入991015B+树索引管理机制Formanismanandmasterofhisfate.599772976372859197rootsqt3阶B+树插入简单示例1544591015213744515920插入202021374420213744152144592021374415214459215997B+树索引管理机制Formanismanandmasterofhisfate.599772976372859197rootsqt3阶B+树插入简单示例15445910152137445159100插入10085919710072100591008591971007291100B+树索引管理机制Formanismanandmasterofhisfate.当删除表里的一条记录时，其对应于索引里的索引条目并不会被物理的删除，只是做了一个删除标记当一个新的索引条目进入一个索引叶子节点的时候，Oracle会检查该叶子节点里是否存在被标记为删除的索引条目，如果存在，则会将所有具有删除标记的索引条目从该叶子节点里物理的删除。当一个新的索引条目进入索引时，oracle会将当前所有被清空的叶子节点（该叶子节点中所有的索引条目都被设置为删除标记）收回，从而再次成为可用索引块。B+树索引的删除管理B+树索引管理机制Formanismanandmasterofhisfate.TheFirstTheSecondTheLast不合理的、较高的PCTFREE。很明显，这将导致索引块的可用空间减少。索引键值持续增加（比如采sequence生成序列号的键值），同时对索引键值按照顺序连续删除，这时可能导致索引碎片的发生。经常被删除或更新的键值，以后几乎不再会被插入时，这种情况与上面的情况类似。尽管被删除的索引条目所占用的空间大部分情况下都能够被重用，但仍然存在一些情况可能导致索引空间被浪费，并造成索引数据块很多但是索引条目很少的后果，这时该索引可以认为出现碎片。而导致索引出现碎片的情况主要包括：B+树索引管理机制Formanismanandmasterofhisfate.B+树索引删除的简单示例删除关键字91599772976372859197rootsqt154459101521374451598597B+树索引管理机制Formanismanandmasterofhisfate.B+树索引删除的简单示例删除关键字91599772976372859197rootsqt15445910152137445159859172915991B+树索引管理机制Formanismanandmasterofhisfate.B+树索引删除的简单示例删除关键字51599772976372859197rootsqt154459101521374451595921374459B+树索引管理机制Formanismanandmasterofhisfate.B+树索引删除的简单示例删除关键字59599772976372859197rootsqt1544591015213744594421374415444497B+树索引管理机制Formanismanandmasterofhisfate.B+树索引删除的简单示例删除关键字636372rootsqt15445910152137445159859172915991727285919151595991449115593B+树索引实现方式Actionspeaklouderthanwords.Youcannotimproveyourpast,butyoucanimproveyourfuture.Oncetimeiswasted,lifeiswasted.B+树索引实现方式Formanismanandmasterofhisfate.下面主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式：MyISAMInnoDBMyISAM是默认存储引擎。它基于更老的ISAM代码，