blogger

    blogger
  • hot log

  • comment

    twitter

    • 空间续费,加上ssl连接。。

      2018-11-22 01:04

    • 12.10.xC6出来时候碰到"Could not determine encryption mode from page zero",竟果然是BUG!http://www-01.ibm.com/support/docview.wss?rs=630&uid=swg21973408

      2015-12-21 20:15

    • 空间已经转移到新加坡,希望会好一些。

      2015-11-16 14:34

    • 增加新域名liaosnet.cc,与liaosnet.com同指向。

      2015-10-09 15:25

    • 空间迁移到香港。或许速度会快一点。。

      2014-02-13 20:10

    • More»

    blog sort

    links

    record

    banner

    理解informix的索引结构

    暗夜星空's Memory from Apr 27 , 2015 at 23:27 PM , under Category:IFX/GBase
        B+ 树是一种树数据结构,通常用于数据库和操作系统的文件系统中。B+ 树的特点是能够保持数据稳定有序,其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入,这与二叉树恰好相反。
        B+ 树在节点访问时间远远超过节点内部访问时间的时候,比可作为替代的实现有着实在的优势。这通常在多数节点在次级存储比如硬盘中的时候出现。通过最大化在每个内部节点内的子节点的数目减少树的高度,平衡操作不经常发生,而且效率增加了。这种价值得以确立通常需要每个节点在次级存储中占据完整的磁盘块或近似的大小。
        B+ 背后的想法是内部节点可以有在预定范围内的可变数目的子节点。因此,B+ 树不需要象其他自平衡二叉查找树那样经常的重新平衡。对于特定的实现在子节点数目上的低和高边界是固定的。例如,在 2-3 B 树(常简称为2-3 树)中,每个内部节点只可能有 2 或 3 个子节点。如果节点有无效数目的子节点则被当作处于违规状态。
        B+ 树的创造者 Rudolf Bayer 没有解释B代表什么。最常见的观点是B代表平衡(balanced),因为所有的叶子节点在树中都在相同的级别上。B也可能代表Bayer,或者是波音(Boeing),因为他曾经工作于波音科学研究实验室。
    注:以上内容来源于维基百科:B+树

        Informix数据库的索引结构使用的是B+树,以下将以示例和图示的方式介绍informix的索引结构,以便于理解。
    1. 创建一个名为t3的测试表,并创建主键(索引)。
    create table "informix".t3 
      (
        id char(8),
        primary key (id) 
      );

    2. 人工生成2万个记录,并导入到表t3中。
    [informix@rhel6u4 ~]$  awk 'BEGIN{for(i=1;i<=20000;i++)printf("%08d\n",i)}' > t3.unl
    [informix@rhel6u4 ~]$  echo "load from t3.unl insert into t3;" | dbaccess testdb –

    3. 通过oncheck -pT testdb:t3命令打印表t3的TBLspace报告信息,重点关注主键信息。
    获取partition partnum:5242917备用;
    了解索引有3层:
    根节点(level 1)占用了1个页(节点),有2个键值,剩余1996字节
    枝节点(level 2)占用了2个页(节点),平均每个节点上有85个键值,
    叶节点(level 3)占用了171个页(节点),平均每个节点上有115个键值。
    点击查看原图
    4. 通过oncheck -pp 5242917 1 命令打印 根节点所在页的信息。
    oncheck -pp partnum logicpagenum 用于打印指定partnum的对应逻辑页,需要使用informix或者root用户执行该指令。逻辑页编号为1的是索引 根节点 所在的页。
    根节点信息相对简单,如上面index usage report中所描述的,仅有两个slot:
    slot 1中00007254指向 枝节点所在的逻辑页 0x7f
    slot 2中 空值 表示大于前一个slot 1的值均指向 枝节点所在的逻辑页 0x7e
    点击查看原图
    5. 通过oncheck -pp 5242917 0x7f 命令打印 枝节点1所在页的信息。
    总共只有62个slot,少于平均值85个,这也是为什么根节点中的第一个键值是00007254的原因。每个slot均是键值8字节(字段大小),加上指针4字节(指向逻辑页)
    如 slot 1中00000117 指向逻辑页0x3,最后一个slot 62的值00007254即是 根节点上索引键值(小于等于该值均位于该枝节点中)指向逻辑页0x3f。
    点击查看原图
    6. 通过oncheck -pp 5242917 0x3 命令打印 页节点1所在页的信息。
    总共有117个slot,接近于平均值116。
    每个slot均是键值8字节(字段大小),加上指针4字节(指向表的rowid),加上删除标识1字节。
    如 slot 1中00000001 指向rowid:0x101,最后一个slot 117的值00000117即是 枝节点1上索引键值(小于等于该值均位于该页节点中)指向rowid:0x175。
    点击查看原图
    7. 索引的整体结构
    按照根节点、枝节点、页节点信息,绘制出该表的索引三层结构图。
    第一层(level 1):仅有 具体键值 和 剩余键值(大于) 两个枝节点;
    第二层(level 2):小于等于具体键值 的枝节点1中含有62个具体键值,并有指向剩余键值(大于)的枝节点2的指针next:0x7e;剩余键值(大于) 的枝节点2中含有108个具体键值 和 1个页节点剩余键值(大于),并有指向枝节点1的指针prev:0x7f;
    第三层(level 3):小于等于具体键值 的页节点1中含有117个具体键值,并有指向下一个页节点2的指针0x2;大于页节点1上所有键值并小于等于枝节点指示具体键值00000234的所有键值位于页节点2上,页节点2上有指向页节点1的指针prev:0x2和指向下一个页节点3的指针0x4;……;枝节点2中的剩余键值(大于)指向的页节点N中含有剩余键值,仅有指向前一个页节点N-1的指针prev:0xad。
    点击查看原图
    非唯一索引的结构
    之前介绍的是三层唯一索引的结构,以下stores_demo库中的表customer上的索引简单介绍 非唯一索引的结构。
    非唯一索引中索引键值,对应的值(表的行)可能不只一个,而是多个。索引键值对应的指向表的rowid(对于页节点)将顺序罗列。对于根节点和枝节点的指向逻辑页的指针,结构上与唯一索引的结构一致。
    点击查看原图