b树索引学习总结

1 / 19 b 树索引学习总结 B树索引学习笔记 、 B树索引解决了传统索引的缺点，效率很高。它放弃索引的排序特征，并保持“平衡”。 注意：下面我们讨论的 B树都是 B+树！ 、 B树的定义此处不介绍，网上很多，可以百度一下，此处看图例： 图 一棵 3 阶 B+树的例子 此处对 B+树要强调一点： B 树的阶数很重要，因为 B数的一些规则都是建立在这个阶数上的。那么请注意几点： 1、根结点特殊，可以不遵守最少充满度规则，可以只有一个键值，两个指针。 2、内结点中的键值都是用来快速找到叶结点的，与数据无关！真正的数据都在叶结点的键值对应的指针中，所有的“ B+子树”都是“中序排序”的，叶结点内部的键值也都是左面比右面小。内结点的键值等于它的右侧指针指向的“ B+子树”的最小键值。 3、每个结点必须充满到一定程度，内结点使用至少：/2 指针，叶结点使用至少 : /2 指向数据的指针。） 、来看一个 3阶的 B+树的规则的例图： 图 B+树的规则 仔细注意：最满情况下的键值个数都为 3。最少情况2 / 19 下就有区别了，内结点 的指针为 /2 2 个，叶结点的键值或指向数据的指针为 /2 2个。主要注意键值个数的区别。 、 B+树上的插入，有以下几种情况： 1、叶结点中还有空间，太幸运了，直接插入到空闲空间即可。图例：插入 32 2、叶结点溢出：就是键值个数超过规定的阶数 n 了，那么只好叶结点分裂，看下图插入 7： 注意分裂方法，因为 B+树所有左面的键值都必须比右面的键值小，那么，就得将小的几个键值放入新分裂出来的左面的叶结点中，至于放入几个，留几个，只要你遵守图中所规定的最少充满度规则即可！上图 中阶数 n=3，根据规则叶结点中最多 3 个键值，最少 /2=2 个键值，所以就分裂成这个样子，不过千万别忘了在父结点中插入新的键值和指针哦。 3、内结点溢出：因为“数据”都在叶结点中，内结点中的键值其实都是“分界点”而已，那么插入数据都是对叶结点进行操作，所以内结点的溢出的根本原因都是因为叶结点的插入引起它的父结点需要增加新键值的情况，当然进而也经常会引起向上逐级新增键值的连锁反应。 看下图插入 160： 这种情况要分裂内结点，记住一定要保持住 B+树的规则。 3 / 19 4、新建根 结点：其实就是内结点分裂的结果，把原来的根结点给分裂了，重新建立一个根结点。 看下图插入 45： 如果如上操作又引起上级内结点的变化，则递归的向上做如上处理，直到符合 B+树的规则为止！ 、 B+树上的删除，有以下几种情况： 1、简单情况：在叶结点删除一个键值后，仍符合 B+树的规则，那么什么也不用做。 这个就不用看图了，呵呵。 2、合并相邻叶节点：如果一个叶结点中删除一个键值后，键值的充满程度不够了，而相邻的一个叶结点中恰好可以容纳下这个结点 中删除后剩余的键值个数，那么就把这些键值都移动到相邻的叶节点中，删除这个叶结点，最后要注意父结点中对应的键值也要删除，如果又改变了 B+树规则，那么递归向上处理！看下图删除 50 : 3、重新分布键值：如果删除一个键值后，相邻的两个叶节点中都无法容纳这些剩余的键值，即两个叶结点的键值数相加大于 n，那么根据 B+树的规则，一定能够满足一个相邻的叶结点，在借一个键值给这个结点后，两个叶结点仍符合 B+ 树的最少充满度规则，那么就借一个键值过来，然4 / 19 后别忘了调整一下父结点的键值，因为它必 须等于它的右侧指针指向的叶结点的最小值。 看下图删除 50： 4、内结点归并：和叶结点如出一辙，只要注意内结点的充满度和叶结点的不同即可，当然如果产生了“连锁反应”，那么就递归的向上做，直到满足规则为止。看下图删除 37： 这里再次强调：一个内结点的键值代表的是：它的右侧指针指向的“ B+子树”的最小键值。这个“ B+子树”有可能只是一个叶结点，比如上图的上图。 扩展思考：其实在真正实现 B+树时，内结点的键值也未必一定等于右侧子树的最小键值，例如当删除一个叶结点的左 侧最小键值后，既然将来并不影响查询操作，所以我们思考一下，是否值得偷偷懒，不去调整父结点对应的键值，小一点就小一点了，不需要做的事就不做，毕竟需要 I/O 代价的呵呵。也许这也是学习的一个方法，思考拓展或者推翻创新 ?。 这部分不要偷懒，多看图例，多思考，如果想仔细研究请多看“数据库系统实现”方面的书中的 B树部分。 By lzq2000 2016-11-3 B树 即二叉搜索树： 5 / 19 1.所有非叶子结点至多拥有两个儿子； 2.所有结点存储 一个关键字； 3.非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树； 如： B树的搜索，从根结点开始，如果查询的关键字与结点的关键字相等，那么就命中； 否则，如果查询关键字比结点关键字小，就进入左儿子；如果比结点关键字大，就进入 右儿子；如果左儿子或右儿子的指针为空，则报告找不到相应的关键字； 如果 B 树的所有非叶子结点的左右子树的结点数目均保持差不多，那么 B 树 的搜索性能逼近二分查找；但它比连续内存空间的二分查找的优点是，改变 B 树结构 不需要移动大 段的内存数据，甚至通常是常数开销； 如： 但 B树在经过多次插入与删除后，有可能导致不同的结构： 右边也是一个 B 树，但它的搜索性能已经是线性的了；同样的关键字集合有可能导致不同的 树结构索引；所以，使用 B树还要考虑尽可能让 B 树保持左图的结构，和避免右图的结构，也就 是所谓的“平衡”问题； 实际使用的 B 树都是在原 B 树的基础上加上平衡算法，即“平衡二叉树”；如何保持 B 树 结点分布均匀的平衡6 / 19 算法是平衡二叉树的关键；平衡算法是一种在 B树中插入和删除结点的 策略； B-树 是一种多路搜索树： 1.定义任意非叶子结点最多只有 M 个儿子；且 M2； 2.根结点的儿子数为 2, M； 3.除根结点以外的非叶子结点的儿子数为 M/2, M； 4.每个结点存放至少 M/2-1 和至多 M-1个关键字； 5.非叶子结点的关键字个数 =指向儿子的指针个数-1； 6.非叶子结点的关键字： K1, K2, , KM-1；且 Ki 7.非叶子结点的指针： P1, P2, , PM；其中 P1指向关键字小于 K1的 子树， PM指向关键字大于 KM-1的子树，其它 Pi指向关键字属于的子树； 8.所有叶子结点位于同一层； 如： B-树的搜索，从根结点开始，对结点内的关键字序列进行二分查找，如果 命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为 空，或已经是叶子结点； B-树的特性： 7 / 19 1.关键字集合分布在整颗树中； 2.任何一个关键字出现且只出现在一个结点中 ； 3.搜索有可能在非叶子结点结束； 4.其搜索性能等价于在关键字全集内做一次二分查找； 5.自动层次控制； 由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少 利用率，其最底搜索性能为： 其中， M为设定的非叶子结点最多子树个数， N为关键字总数； 所以 B-树的性能总是等价于二分查找，也就没有 B树平衡的问题； 由于 M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占 M/2 的结点；删除结点 时，需将两个不足 M/2 的兄弟结点合并； B+树 B+树是 B-树的变体，也是一种多路搜索树： 1.其定义基本与 B-树同，除了： 2.非叶子结点的子树指针与关键字个数相同； 3.非叶子结点的子树指针 Pi，指向关键字值属于Ki, Ki+1)的子树 ； 5.为所有叶子结点增加一个链指针； 8 / 19 6.所有关键字都在叶子结点出现； 如： B+的搜索与 B-树也基本相同，区别是 B+树只有达到叶子结点才命中， 其性能也等价于在关键字全集做一次二分查找； B+的特性： 1.所有关键字都出现在叶子结点的链表中，且链表中的关键字恰好 是有序的； 2.不可能在非叶子结点命中； 3.非叶子结点相当于是叶子结点的索引，叶子结点相当于是存储 数据的数据层； 4.更适合文件索引系统； B*树 是 B+树的变体，在 B+树的非根和非叶子结点再增加指向兄弟的指针； B*树定义了非叶子结点关键字个数至少为 *M，即块的最低使用率为 2/3 ； B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中 1/2 的数据 复制到新结点，最后在父结点中增加新结点的指针； B+树的分裂只影响原结点和父 结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针； B*树的分裂：当一个结点满时，如果它的下一个兄9 / 19 弟结点未满，那么将一部分 数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字 ；如果兄弟也满了，则在原结点与兄弟结点之 间增加新结点，并各复制 1/3的数据到新结点，最后在父结点增加新结点的指针； 所以， B*树分配新 结点的概率比 B+树要低，空间使用率更高； 小结 B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于 走右结点； B-树：多路搜索树，每个结点存储 M/2 到 M 个关键字，非叶子结点存储指向关键 字范围的子结点； 所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中； B+树：在 B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点 中出现，非叶子结点作为叶子结点的索引； B+树总是到叶子结点才命中； B*树：在 B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率 摘要：本文对 B 树索引的结构、内部管理等方面做了一个全面的介绍。同时深入探讨了一些与 B树索引有关的广为流传的说法，比如删除记录对索引的影响，定期重建索引能解决许多性能10 / 19 问题等。 树索引的相关概念 索引与表一样，也属于段的一种。里面存放了用户的数据，跟表一样需要占用磁盘空间。只不过，在索引里的数据存放形式与表里的数据存放形式非常的不一样。在理解索引时，可以想象一本书，其中书的内容就相当于表里的数据，而书前 面的目录就相当于该表的索引。同时，通常情况下，索引所占用的磁盘空间要比表要小的多，其主要作用是为了加快对数据的搜索速度，也可以用来保证数据的唯一性。 但是，索引作为一种可选的数据结构，你可以选择为某个表里的创建索引，也可以不创建。这是因为一旦创建了索引，就意味着 oracle 对表进行 DML 时，必须处理额外的工作量以及存储方面的开销。所以创建索引时，需要考虑创建索引所带来的查询性能方面的提高，与引起的额外的开销相比，是否值得。 从物理上说，索引通常可以分为：分区和非分区索引、常规 B 树索引 、位图索引、翻转索引等。其中， B 树索引属于最常见的索引，由于我们的这篇文章主要就是对 B 树索引所做的探讨，因此下面只要说到索引，都是指 B 树索引。 B 树索引是一个典型的树结构，其包含的组件主要是： 11 / 19 叶子节点：包含条目直接指向表里的数据行。 分支节点：包含的条目指向索引里其他的分支节点或者是叶子节点。 根节点：一个 B 树索引只有一个根节点，它实际就是位于树的最顶端分支节点。 可以用下图一来描述 B树索引的结构。其中， B表示分支节点，而 L表示叶子节点。 对于分支节点块来说，其所包含的索引条目都是按照顺序排列的。每个索引条目都具有两个字段。第一个字段表示当前该分支节点块下面所链接的索引块中所包含的最小键值；第二个字段为四个字节，表示所链接的索引块的地址，该地址指向下面一个索引块。在一个分支节点块中所能容纳的记录行数由数据块大小以及索引键值的长度决定。比如从上图一可以看到，对于根节点块来说，包含三条记录，分别为、，它们指向三个分支节点块。其中的 0、 500和 1000分别表示这三个分支节点块所链接的键值的最小值。而 B1、 B2和 B3则表示所指向的三个分支节点块的地 址。 对于叶子节点块来说，其所包含的索引条目与分支节点一样，都是按照顺序排列的。每个索引条目也具有两个字段。第一个字段表示索引的键值，对于单列索引来说是一个值；而对于多列索引来说则是多个值组合在一起的。第二个字段表示键值所对应的记录行的 ROWID，该 ROWID 是记录行在表里的物理地址。如果索引是创建在非分区表上或者索12 / 19 引是分区表上的本地索引的话，则该 ROWID占用 6 个字节；如果索引是创建在分区表上的全局索引的话，则该 ROWID 占用 10个字节。 知道这些信息以后，我们可以举个例子来说明如 何估算每个索引能够包含多少条目，以及对于表来说，所产生的索引大约多大。对于每个索引块来说，缺省的 PCTFREE 为10，也就是说最多只能使用其中的 90。同时 9i 以后，这 90中也不可能用尽，只能使用其中的 87左右。也就是说， 8KB 的数据块中能够实际用来存放索引数据的空间大约为 6488个字节。 假设我们有一个非分区表，表名为 warecountd，其数据行数为 130万行。该表中有一个列，列名为 goodid，其类型为 char，那么也就是说该 goodid的长度为固定值： 8。同时在该列上创建了一个 B树 索引。 在叶子节点中，每个索引条目都会在数据块中占一行空间。每一行用 2 到 3 个字节作为行头，行头用来存放标记以及锁定类型等信息。同时，在第一个表示索引的键值的字段中，每一个索引列都有 1个字节表示数据长度，后面则是该列具体的值。那么对于本例来说，在叶子节点中的一行所包含的数据大致如下图二所示： 从上图可以看到，在本例的叶子节点中，一个索引条目占 18 个字节。同时我们知道 8KB 的数据块中真正可以13 / 19 用来存放索引条目的空间为 6488 字节，那么在本例中，一个数据块中大约可以放 360个索引条目。而对 于我们表中的130万条记录来说，则需要大约 3611个叶子节点块。 而对于分支节点里的一个条目来说，由于它只需保存所链接的其他索引块的地址即可，而不需要保存具体的数据行在哪里，因此它所占用的空间要比叶子节点要少。分支节点的一行中所存放的所链接的最小键值所需空间与上面所描述的叶子节点相同；而存放的索引块的地址只需要 4 个字节，比叶子节点中所存放的 ROWID 少了 2 个字节，少的这2 个字节也就是 ROWID 中用来描述在数据块中的行号所需的空间。因此，本例中在分支节点中的一行所包含的数据大致如下图三所示： 从上图可以看到，在本例的分支节点中，一个索引条目占 16 个字节。根据上面叶子节点相同的方式，我们可以知道一个分支索引块可以存放大约 405个索引条目。而对于我们所需要的 3611 个叶子节点来说，则总共需要大约 9 个分支索引块。 这样，我们就知道了我们的这个索引有 2 层，第一层为 1个根节点，第二层为 9个分支节点，而叶子节点数为3611个，所指向的表的行数为 1300000行。但是要注意，在oracle 的索引中，层级号是倒过来的，也就是说假设某个索引有 N 层，则根节点的层级号为 N，而根节点下一层的分支14 / 19 节点的 层级号为 N-1，依此类推。对本例来说， 9 个分支节点所在的层级号为 1，而根节点所在的层级号为 2。 2. 树索引的内部结构 我们可以使用如下方式将 B 树索引转储成树状结构的形式而呈现出来： alter session set events immediate trace name treedump level INDEX_OBJECT_ID; 比如，对于上面的例子来说，我们把创建在 goodid上的名为 idx_warecountd_goodid 的索引 转储出来。 SQL select object_id from user_objects where object_name=IDX_WARECOUNTD_GOODID; OBJECT_ID - 7378 SQL alter session set events immediate trace name treedump level 7378; 打开转储出来的文件以后，我们可以看到类 似下面的内容： - begin tree dump 15 / 19 branch: 0x180eb0a 25225994 branch: 0x180eca1 25226401 leaf: 0x180eb0b 25225995 leaf: 0x180eb0c 25225996 leaf: 0x180eb0d 25225997 leaf: 0x180eb0e 25225998 branch: 0x180ee38 25226808 leaf: 0x180eca0 25226400 leaf: 0x180eca2 25226402 leaf: 0x180eca3 25226403 leaf: 0x180eca4 25226404 其中，每一行的第一列表示节点类型： branch 表示分支节点，而 leaf 则表示叶子节点；第二列表示十六进制表示的节点的地址；第三列表示十进制表示的节点的地址；第四列表示相对 于前一个节点的位置，根节点从 0开始计算，其他分支节点和叶子节点从 -1 开始计算；第五列的 ow 表示当前节点中所含有的索引条目的数量。比如我们可以看到根节点中含有的 ow为 9，表示根节点中含有 9 个索引条目，分别指向 9 个分支节点；第六列中的 level 表示分支节点的层级，对于叶子节点来说 level都是 0。第六列中的 rrow表示16 / 19 有效的索引条目的数量，比如对于第一个 leaf 来说，其 rrow为 359，也就是说该叶子节点中存放了 359 个可用索引条目，分别指向表 warecountd 的 359 条记录。 上面这种方式以树状 形式转储整个索引。同时，我们可以转储一个索引节点来看看其中存放了些什么。转储的方式为： alter system dump datafile file# block block#; 我们从上面转储结果中的第二行知道，索引的根节点的地址为 25225994，因此我们先将其转换为文件号以及数据块号。 SQL select dbms_block_address_file, 2 dbms_block_address_block from dual; DBMS_BLOCK_ADDRES DBMS_BLOCK_ADDRES - - 6 60170 于是，我们转储根节点的内容。 SQL alter system dump datafile 6 block 60170; 打开转储出来的跟踪文件，我们可以看到如下的索17 / 19 引头部的内容： header address 85594180=0x51a1044 kdxcolev 2 KDXCOLEV Flags = - - - kdxcolok 0 kdxcoopc 0x80: pcode=0: iot flags=- is converted=Y kdxconco 2 kdxcosdc 0 kdxcoo 8 kdxcofbo 44=0x2c kdxcofeo 7918=0x1eee kdxcoavs 7874 kdxbrlmc 25226401=0x180eca1 kdxbrsno 0 kdxbrbksz 8060 其中的 kdxcolev表示索引层级号，这里由于我们转储的是根节点，所以其层级号为 2。对叶子节点来说该值为0； kdxcolok表示该索引上是否正在发生修改块结构的事务；kdxcoopc 表示内部操作代码； k