精华内容
下载资源
问答
  • 文件组织:索引顺序文件

    千次阅读 2013-11-08 23:42:39
    ISAM文件和VSAM文件是常用的索引顺序文件。...由于磁盘是以盘组、柱面和磁道三级地址存取的设备,则可磁盘上的数据文件建立盘组、柱面和磁道多级索引,下面只讨论在同一个盘组上建立的ISAM文件

    索引文件构成     

    链接地址:http://student.zjzk.cn/course_ware/data_structure/web/wenjian/wenjian10.3.1.htm

    1.索引文件

         索引文件由主文件和索引表构成。
      ①主文件:文件本身。
      ②索引表:在文件本身外建立的一张表,它指明逻辑记录和物理记录之间的一一对应关系。

    2.索引表组成
         索引表由若干索引项组成。一般索引项由主关键字和该关键字所在记录的物理地址组成。
      注意:
         索引表必须按主关键字有序,而主文件本身则可以按主关键字有序或无序。

    3.索引顺序文件和索引非顺序文件
    (1)索引顺序文件(Indexed Sequential File)
         主文件按主关键字有序的文件称索引顺序文件。
         在索引顺序文件中,可对一组记录建立一个索引项。这种索引表称为稀疏索引。

    (2)索引非顺序文件(Indexed NonSequentail File)
         主文件按主关键字无序得文件称索引非顺序文件。
         在索引非顺序文件中,必须为每个记录建立一个索引项,这样建立的索引表称为稠密索引。
      注意:
         ① 通常将索引非顺序文件简称为索引文件。
         ② 索引非顺序文件主文件无序,顺序存取将会频繁地引起磁头移动,适合于随机存取,不适合于顺序存取。
         ③ 索引顺序文件的主文件是有序的,适合于随机存取、顺序存取。
         ④ 索引顺序文件的索引是稀疏索引。索引占用空间较少,是最常用的一种文件组织。
         ⑤ 最常用的索引顺序文件:ISAM文件和VSAM文件。

    索引文件的存储

    1.索引文件的存储
         索引文件在存储器上分为两个区:索引区和数据区。索引区存放索引表,数据区存放主文件。

    2. 索引文件的建立
         建立索引文件的过程:
      (1) 按输入记录的先后次序建立数据区和索引表。其中索引表中关键字是无序的
      (2) 待全部记录输入完毕后对索引表进行排序,排序后的索引表和主文件一起就形成了索引文件。
      【例】对于表10.2的数据文件,主关键字是职工号,排序前的索引表如表10.3所示,排序后的索引表见表10.4,表10.2和表10.4一起形成了一个索引文件。



    ISAM文件和VSAM文件是常用的索引顺序文件。


    ISAM文件

         ISAM为Indexed Sequential Access Methed(索引顺序存取方法)的缩写,它是一种专为磁盘存取文件设计的文件组织方式,采用静态索引结构。由于磁盘是以盘组、柱面和磁道三级地址存取的设备,则可对磁盘上的数据文件建立盘组、柱面和磁道多级索引,下面只讨论在同一个盘组上建立的ISAM文件。

    1、ISAM文件的组成
         ISAM文件由多级主索引、柱面索引、磁道索引和主文件组成。
         文件的记录在同一盘组上存放时,应先集中放在一个柱面上,然后再顺序存放在相邻的柱面上。对同一柱面,则应按盘面的次序顺序存放。
    【例】图10.4所示的文件是存放在同一个磁盘组上的ISAM文件。
    【数据结构】文件:索引顺序文件 - 八月照相馆 - 八月照相馆
    【数据结构】文件:索引顺序文件 - 八月照相馆 - 八月照相馆
     
         


    其中:
      ① C表示柱面;
         ② T表示磁道;
         ③ C i T i 表示i号柱面,j号磁道;
         ④ R i 表示主关键字为i的记录。
    分析:
         从图中可看出,主索引是柱面索引的索引,这里只有一级主索引。若文件占用的柱面索引很大,使得一级主索引也很大时,可采用多级主索引。当然,若柱面索引较小时,则主索引可省略。
         通常主索引和柱面索引放在同一个柱面上(如图10.4是放在0号柱面上),主索引放在该柱面最前的-个磁道上,其后的磁道中存放柱面索引。每个存放主文件的柱面都建立有一个磁道索引,放在该柱面的最前面的磁道To上,其后的若干个磁道是存放主文件记录的基本区,该柱面最后的若干个磁道是溢出区。基本区中的记录是按主关键字大小顺序存储的,溢出区被整个柱面上的基本区中各磁道共享,当基本区中某磁道溢出时,就将该磁道的溢出记录,按主关键字大小链成一个链表(以下简称溢出链表)放人溢出区。

    2、各级索引中的索引项结构

    【数据结构】文件:索引顺序文件 - 八月照相馆 - 八月照相馆
     

        注意:
         磁道索引中的每一个索引项,都由两个子索引项组成:基本索引和溢出索引项。

    3、ISAM文件的检索
      在ISAM文件上检索记录时,从主索引出发,找到相应的柱面索引;从柱面索引找到记录所在柱面的磁道索引;从磁道索引找到记录所在磁道的起始地址,由此出发在该磁道上进行顺序查找,直到找到为止。若找遍该磁道均不存在此记录,则表明该文件中无此记录;若被查找的记录在溢出区,则可从磁道索引项的溢出索引项中得到溢出链表的头指针,然后对该表进行顺序查找。
      【例】要在下图中查找记录R78,先查主索引,即读入CoTo;因为78<300,则查找柱面索引的C0Tl(不妨设每个磁道可存放5个索引项),即读人C0Tl;因为70<78<150,所以进一步把C2T0入内存;查磁道索引,因为78<81,所以C2T1即为R78所存放的磁道,读人C2T1,后即可查得R78
    【数据结构】文件:索引顺序文件 - 八月照相馆 - 八月照相馆
     
      为了提高检索效率,通常可让主索引常驻内存,并将柱面索引放在数据文件所占空间居中位置的柱面上,这样,从柱面索引查找到磁道索引时,磁头移动距离的平均值最小。

    4、ISAM文件的插入操作
      当插人新记录时,首先找到它应插入的磁道。若该磁道不满,则将新记录插入该磁道的适当位置上即可;若该磁道已满,则新记录或者插在该磁道上,或者直接插入到该磁道的溢出链表上。插入后,可能要修改磁道索引中的基本索引项和溢出索引项。
      【例】依次将记录R 72,R 87,R 91插入到上图所示的文件后,第二个柱面的磁道索引及该柱面中主文件W的变化状况如下图所示。
    【数据结构】文件:索引顺序文件 - 八月照相馆 - 八月照相馆
     
      
      当插入R 72时,应将它插在C 2T l,因为72<75,所以R 72应插在该磁道的第一个记录的位置上,而该磁道上原记录依次后移一个位置,于是最后一个记录R 81被移人溢出区。由于该磁道上最大关键字由81变成79,故它的溢出链表也由空变为含有一个记录R 81的非空表。因此,将C2T1对应的磁道索引项中基本索引项的最大关键字,由81改为79;将溢出索引项的最大关键字置为81,且令溢出链表的头指针指向R 81,的位置;类似地,R87和B91被先后插入到第2号柱面的第2号磁道C 2T 2上。插入R 87时,R 100被移到溢出区;插入R 91时,R 95被移到溢出区,即该磁道溢出链表上有两个记录。虽然物理位置上R 100在R 95,之前,但作为按关键字有序的链表,B 95是链表上的第一个记录,R 100是第二个记录。因此,C 2T 2对应的溢出索引项中,最大关键字为100,而溢出链表头指针指向R95的位置;C 2T 2移出R 95和移出R 100后,92变为该磁道上最大关键字,所以C 2T 2对应的基本索引项中最大关键字由100变为92。


    5、ISAM文件中删除记录的操作
      ISAM文件中删除记录的操作,比插入简单得多,只要找到待删除的记录,在其存储位置上作删除标记即可,而不需要移动记录或改变指针。在经过多次的增删后,文件的结构可能变得很不合理。此时,大量的记录进入溢出区,而基本区中又浪费很多的空间。因此,通常需要周期性地整理ISAM文件,把记录读入内存重新排列,复制成一个新的ISAM文件,填满基本区而空出溢出区。


    VSAM文件

         VSAM是Virtual Storage Access Method(虚拟存储存取方法)的缩写,它也是一种索引顺序文件的组织方式,采用B+树作为动态索引结构。

    1、B+树
         B+树是一种常用于文件组织的B-树的变型树。一棵m阶的B+树和m阶的B-树的差异是:
      ①有k个孩子的结点必有k个关键字;
      ②所有的叶结点,包含了全部关键字的信息及指向相应的记录的指针,且叶子结点本 身依照关键字的大小,自小到大顺序链接;
      ③上面各层结点中的关键字,均是下一层相应结点中最大关键字的复写(当然也可采用"最小关键字复写"的原则),因此,所有非叶结点可看作是索引部分。
    【例】下图是一棵3阶的B+树。


    【数据结构】文件:索引顺序文件 - 八月照相馆 - 八月照相馆
     



      注意: 
         ①通常在B+树上有两个头指针root和sqt,前者指向根结点,后者指向关键字最小的叶子结点。
         ②对B+树可进行两种查找运算:一种是从最小关键字起进行顺序查找;另一种是从根结点开始进行随机查找。

    2、B+树的运算
         在B+树上进行随机查找、插入和删除的过程,基本上与B-树类似。

    (1)B+树的查找运算
         在查找时,若非叶结点上的关键字等于给定值,并不终止,而是继续向下直到叶子结点。因此,在B+树中,不管查找成功与否,每次查找都是走了一条从根到叶子结点的路径。
         B+树查找的分析类似于B-树。B+树的插入也仅在叶子结点上进行,当结点中的关键字个数大于m时要分裂成两个结点,它们所含关键字的个数分别为:
         【数据结构】文件:索引顺序文件 - 八月照相馆 - 八月照相馆 
    并且它们的双亲结点中应同时包含这两个结点的最大关键字。

    (2)B+树的删除
         B+树的删除仅在叶子结点进行,当叶子结点中的最大关键字被删除时,其在非终端结点中的值可以作为一个"分界关键字"存在。若因删除而使结点中关键字的个数少于  【数据结构】文件:索引顺序文件 - 八月照相馆 - 八月照相馆 时,则可能要和该结点的兄弟结点合并,合并过程和B-树类似。

    3、VSAM文件
         B+树的每个叶结点中的关键字均对应一个记录,适宜于作为稠密索引。但若让叶结点中的关键字对应一个页块,则B+树可用来作为稀疏索引。IBM公司VSAM文件是用B+树作为文件的稀疏索引的一个典型例子。
         这种文件组织的实现,使用了IBM370系列的操作系统的分页功能,这种存取方法与存储设备无关,与柱面、磁道等物理存储单位没有必然的联系。例如,可以在一个磁道中放n个控制区间,也可以一个控制区间跨n个磁道。

    (1)VSAM文件的结构
         VSAM文件的结构由三部分组成:索引集顺序集数据集(如下图所示)。
    【数据结构】文件:索引顺序文件 - 八月照相馆 - 八月照相馆
     
           
       ①数据集
         文件的记录均存放在数据集中。数据集中的一个结点称为控制区间(Control Interval),它是一个I/0操作的基本单位,每个控制区间含有一个或多个数据记录。

       ②顺序集和索引集
         顺序集和索引集一起构成一棵B+树,作为文件的索引部分。
         顺序集中存放的每个控制区间的索引项由两部分信息组成:该控制区间中的最大关键字和指向控制区间的指针。若干相邻的控制区间的索引项,形成顺序集中的一个结点。结点之间用指针相链接,而每个结点又在其上一层的结点中建有索引,且逐层向上建立索引,所有的索引项都由最大关键字和指针两部分信息组成。这些高层的索引项形成B+树的非终端结点。
         VSAM文件既可在顺序集中进行顺序存取,又可从最高层的索引(B+树的根结点)出发,进行按关键字的随机存取。顺序集中一个结点连同其对应的所有控制区间形成一个整体,称做控制区域(Control Range),它相当于ISAM文件中的一个柱面,而控制区间相当于一个磁道。

    (2)VSAM文件中控制区间的结构
         在VSAM文件中,记录可以是不定长的。因而在控制区间中,除了存放记录本身之外,还有每个记录的控制信息(如记录的长度等)和整个区间的控制信息(如区间中存放的记录数等),控制区间的结构如下表所示。

    【数据结构】文件:索引顺序文件 - 八月照相馆 - 八月照相馆
     

    (3)VSAM文件的插入方法

         VSAM文件中没有溢出区,解决插入的方法是在初建文件时留出空间:一是每个控制区间内并未填满记录,而是在最末一个记录和控制信息之间留有空隙;二是在每个控制区域中有一些完全空的控制区间,并在顺序集的索引中指明这些空区间。
         当插入新记录时,大多数的新记录能插入到相应的控制区间内,但要注意:为了保持区间内记录的关键字从小至大有序,则需将区间内关键字大于插入记录关键字的记录,向控制信息的方向移动。若在若干记录插入之后控制区间已满,则在下一个记录插入时,要进行控制区间的分裂,即把近乎一半的记录移到同一控制区域内全空的控制区间中,并修改顺序集中相应索引。倘若控制区域中已经没有全空的控制区间,则要进行控制区域的分裂,此时顺序集中的结点亦要分裂,由此需要修改索引集中的结点信息。但由于控制区域较大,通常很少发生分裂的情况。

    (4)VSAM文件的删除

         在VSAM文件中删除记录时,需将同一控制区间中,比删除记录关键字大的记录向前移动,把空间留给以后插人的新记录。若整个控制区间变空,则回收作空闲区间用,且需删除顺序集中相应的索引项。

    (5)VSAM文件的优点
         和ISAM文件相比,基于B+树的VSAM文件有如下优点:能保持较高的查找效率,查找一个后插入记录和查找一个原有记录具有相同的速度;动态地分配和释放存储空间,可以保持平均75%的存储利用率;而且永远不必对文件进行再组织。因而基于B+树的VSAM文件,通常被作为大型索引顺序文件的标准组织。
    展开全文
  • 代码编译的结果从本地机器码转变为字节码,是存储格式发展的小步,却是编译发展的大步。...访问标志、类索引、父类索引与接口索引集合、字段集合、属性集合 、各数据项的定义、作用、结构组成及实例讲解

    代码编译的结果从本地机器码转变为字节码,是存储格式发展的一小步,却是编译发展的一大步。

    上篇博文中学习讲解了Class类文件结构的有关知识点,关于数据项方面介绍了常量池,此篇文章将介绍完余下的数据项部分,大致知识点如下:

    • 访问标志
    • 类索引、父类索引与接口索引集合
    • 字段表集合
    • 属性表集合
    • 各数据项的定义、作用、结构组成及实例讲解

    JVM高级特性与实践(一):Java内存区域 与 内存溢出异常
    JVM高级特性与实践(二):对象存活判定算法(引用) 与 回收
    JVM高级特性与实践(三):垃圾收集算法 与 垃圾收集器实现
    JVM高级特性与实践(四):内存分配 与 回收策略
    JVM高级特性与实践(五):实例探究Class类文件 及 常量池
    JVM高级特性与实践(七):九大类字节码指令集(实例探究 )
    JVM高级特性与实践(八):虚拟机的类加载机制
    JVM高级特性与实践(九):类加载器 与 双亲委派模式(自定义类加载器源码探究ClassLoader)
    JVM高级特性与实践(十):虚拟机字节码执行引擎(栈帧结构)
    JVM高级特性与实践(十一):方法调用 与 字节码解释执行引擎(实例解析)
    JVM高级特性与实践(十二):Java内存模型 与 高效并发时的内外存交互(volatile变量规则)
    JVM高级特性与实践(十三):线程实现 与 Java线程调度
    JVM高级特性与实践(十四):线程安全 与 锁优化


    一. Class类文件中的部分结构

    0. 测试的实例

    (1)示例源码

    以下简单代码作为后续讲解的事例,代码如下:

    package org.fenixsoft.clazz;
    
    public class TestClass {
    
        private int m;
    
        public int inc() {
            return m + 1;
        }
    }

    (2)Class文件

    下图显示的是使用十六进制编辑器WinHex打开Class文件结果:

    这里写图片描述

    (3)TestClass.class文件字节码

    以下是TestClass.class文件字节码内容(省略了常量池以外的信息):

    d:\>javap -verbose Test  
    Compiled from "Test.java"  
    public class com.test.Test extends java.lang.Object  
      SourceFile: "Test.java"  
      minor version: 0  
      major version: 49  
      Constant pool:  
    const #1 = class        #2;     //  com/test/Test   
    const #2 = Asciz        com/test/Test;  
    const #3 = class        #4;     //  java/lang/Object   
    const #4 = Asciz        java/lang/Object;  
    const #5 = Asciz        m;  
    const #6 = Asciz        I;  
    const #7 = Asciz        <init>;  
    const #8 = Asciz        ()V;  
    const #9 = Asciz        Code;  
    const #10 = Method      #3.#11; //  java/lang/Object."<init>":()V  
    const #11 = NameAndType #7:#8;//  "<init>":()V  
    const #12 = Asciz       LineNumberTable;  
    const #13 = Asciz       LocalVariableTable;  
    const #14 = Asciz       this;  
    const #15 = Asciz       Lcom/test/Test;;  
    const #16 = Asciz       getM;  
    const #17 = Asciz       ()I;  
    const #18 = Field       #1.#19; //  com/test/Test.m:I  
    const #19 = NameAndType #5:#6;//  m:I  
    const #20 = Asciz       SourceFile;  
    const #21 = Asciz       Test.java;  


    1. 访问标志

    (1)作用

    常量池之后的数据结构是访问标志(access_flags),这个标志主要用于识别一些类或者接口层次的访问信息,主要包括:

    • 这个Class是类还是接口;
    • 是否定义为public类型;
    • 是否定义abstract类型;
    • 如果是类的话是否被声明为final;

    以上只是举的几个例子,具体的标志位以及标志的含义如下:

    (2)组成

    这里写图片描述

    如上所示,访问标志中一共有16个标志位可以使用,当前只制定了8个。

    (3)例子实践

    以开头的简单代码为例,TestClass是一个普通Java类,不是接口、枚举或注解,被public关键字修饰但没有被声明为final 和 abstract,因此它的 ACC_PUBLIC、ACC_SUPER标志应为真,其余的标志位为假,它的 access_flags 值应为:0x0001|0x0020 = 0x0021,从下图可看验证推理正确:

    这里写图片描述



    2. 类索引、父类索引与接口索引集合

    (1)定义与作用

    类索引(this_class)父类索引(super_class)都是一个 u2 类型的数据,而接口索引集合(interfaces)一组 u2类型的数据集合,Class文件中由这三项数据来确定类的继承关系。

    • 类索引:用来确定这个类的全限定名;
    • 父类索引:用来确定这个类的父类的全限定名。由于Java语言不允许多重继承,所以父类索引只有一个,除了 java.lang.Object 之外,所有的Java类都有父类。因此除了java.lang.Object 外,所有Java类的父类索引都不为0。
    • 接口索引:用来描述这个类实现了哪些接口。这些被实现的接口将按 implement 语句(若此类本身是一个接口,则应当是extend语句)后的接口顺序从左到右排列在接口索引集合中。

    (2)类索引查找

    类索引、父类索引、接口索引都按照顺序排列在访问标志之后,类索引和父类索引用两个 u2 类型的索引值表示,它们各自指向一个类型为 CONSTANT_Class_info 的类描述符常量,而在上一篇博文中讲过,通过CONSTANT_Class_info 类型常量中的索引值可以找到定义在 CONSTANT_Utf8_info类型常量中的全限定名字符串。下图所示为类索引查找过程:

    这里写图片描述

    (3)接口计数器

    对于接口索引集合,入口的第一项——u2 类型的数据为接口计数器(interfaces_count),表示索引表的容量。如果该类没有实现任何接口,则该计数器为0,后面接口的索引表不再占用任何字节。示例代码中的类索引、父类索引、接口索引的内容如下图:

    这里写图片描述

    查看上图可知,从偏移地址 0x000000F1 开始的3个 u2 类型的值分别为 0x0001、0x0003、0x0000,代表着类索引为1、父类索引为3、接口索引集合为0。


    3. 字段表集合

    (1)定义与作用

    字段表(field_info)用于描述接口或者类中声明的变量。字段(field)包括类级变量和实例级变量,但是不包括方法内部声明的局部变量。

    (2)字段表结构

    可以想一想在Java中描述一个字段可以包含什么信息?可以包括的信息有:

    • 字段的作用域(public、private、protected修饰符)
    • 是实例变量还是类变量(static修饰符)
    • 可变性(final)
    • 并发可见性(volatile修饰符,是否强制从主内存读写)
    • 是否被序列化(transient修饰符)
    • 字段数据类型(基本类型、对象、数组)
    • 字段名称

    在上述这些信息中,各个修饰符都是布尔值,要么有某个修饰符,要么没有,很适合使用标志位来表示。而字段叫什么名字、被定义成什么数据类型都是无法固定的,只能引用常量池中的常量来描述。下表列出了字段表的最终格式:

    这里写图片描述

    • access_flags:是一个 u2的数据类型。
    • name_index 索引值: 对常量池的引用,代表着字段的简单名称。
    • descriptor_index 索引值: 对常量池的引用,代表字段和方法的描述符。

    (3)字段访问标志 access_flags

    字段修饰符放在 access_flags 项目中,它与类中的 access_flags 项目是非常类似的,都是一个 u2的数据类型,其中可以设置的标志位和含义如下:

    这里写图片描述

    由于Java本身的语言规则决定,在实际情况中有诸如此类的规则,以下举例部分现象:

    • ACC_PUBLIC、ACC_PRIVATE、ACC_PROTECTED三个标志中只能选其一;
    • ACC_FINAL、ACC_VOLATILE不能同时选择;
    • 接口之中的字段必须有 ACC_PUBLIC、ACC_STATIC、ACC_FINAL标志。

    (4)“简单名称”、“描述符”、“全限定名”解释

    全限定名:以示例中的代码为例,“org/fenixsoft/clazz/TestClass”是这个类的全限定名,仅仅是把类全名的“.”替换成了“/”,为了使连续的多个全限定名之间不产生混淆,最后一班加个“;”代表全限定名结束。

    简单名称:指没有类型和参数修饰的方法或字段名称,这个类中的inc() 方法和 m字段的简单名称是“inc”和“m”。

    描述符

    作用是用来描述字段的数据类型、方法的参数列表(包括数量、类型以及顺序)和返回值。根据描述规则,基本数据类型(byte、char、float、double、short、int、long、boolean)以及代表无返回值的void类型都用一个大写字符表示,而对象类型则用字符L加对象的全限定名来表示,如下图:

    这里写图片描述

    对于数组类型,每一维度将使用一个前置的“[”字符来描述,例如“int[]”将被记录为“[I”。

    用描述符来描述方法时,按照先参数列表,后返回值的顺序描述,参数列表按照参数的严格顺序放在一组小括号“()”内。举个例子:方法void inc() 的描述符为“()V”。

    (5)实例讲解

    这里写图片描述

    结合上图与代码TestClass.class 文件而言,字段表集合从地址 0x000000F8开始:

    • 第一个u2类型的数据为容量计数器fields_count,其值为0x0001,说明这个类只有一个字段表数据。
    • 接下来紧跟的是 access_flags标志,其值为0x0002,代表private修饰符的ACC_PRIVATE标志位为真(ACC_PRIVATE标志的值为0x0002) 。
    • 代表字段名称name_index值为0x0005,从上篇博文中的常量表可查出第5项常量是一个 CONSTANT_Utf8_info类型的字符串,其值为“m”。
    • 代表字段描述符descriptor_index 的值为0x0006,指向常量池的字符串“I”。

    根据以上信息,可以推断出原代码定义为“private int m;”。



    4. 方法表集合

    (1)结构

    Class文件存储格式中对方法表的描述与字段表是一致的,包括了:

    • 访问标志(access_flags)
    • 名称索引(name_index)
    • 描述符索引(descriptor_index)
    • 属性表集合(attributes)

    这些数据项目的含义也非常类似,仅在访问标志和属性表集合的可选项中有区别:

    这里写图片描述

    (2)方法表与字段表的区别

    区别在于访问标志的不同:在方法中不能了用volatiletransient关键字修饰,所以方法表中无ACC_VOLATILE、ACC_TRANSIENT。与之相对的 synchronizednativestrictfpabstract关键字可修饰方法,所以在方法表中就增加了相应的访问标志。

    (3)标志位

    对于方法表,所有的标志位及取值如下表:

    这里写图片描述

    行文自此,你会发现方法的定义可以通过访问标志、名称索引、描述符索引表达清楚,但是方法里的代码去哪里了?

    方法里的Java代码,经过编译器编译成字节码指令后,存放在方法属性表集合一个名为“Code”属性里,属性表作为Class文件格式中最具扩展性的一种数据项目,在后续会详细讲解。

    (4)实例讲解

    这里写图片描述

    还是以示例代码为例,方法表集合的入口地址为 0x00000101:

    • 第一个u2 类型的数据(即计数器容量)的值为0x0002,代表集合中有两个方法(这两个方法是编译器添加的实例构造器和源码中的方法inc())。
    • 第一个方法的访问标识值是0x001,也就是只有ACC_PUBLIC 标志为真。
    • 名称索引为0x0007,查找常量池表可知对应的方法名是“”。
    • 描述符索引值为 0x0008,对应常量为“()V”。
    • 属性表计数器 attributes_count的值为0x0001,表示此方法的属性表集合有一项属性。
    • 属性名称索引为 0x0009,对应常量为“Code”,说明此属性是方法的字节码描述。



    二. 属性表集合

    由于这一部分内容较多,所以另起一点进行讲解。

    0. 属性表

    属性表(attribute_info)在Class文件、字段表、方法表都可以携带自己的属性集合,用于描述某些场景专有的信息。

    与Class文件中的其它数据项木要求严格的顺序、长度和内存不同,属性表集合限制稍宽松,不再要求各个属性表具有严格顺序,只要不与已有属性名重复,任何人实现的二便一起都可以想属性表中写入自己定义的属性信息,而Java虚拟机会忽略掉它不认识的属性。

    下表对其中的一些属性中关键常用部分进行讲解:

    这里写图片描述

    对于每个属性,它的名称需要从常量池中引入一个 CONSTANT_Utf8_info类型的常量来表示,而属性值的结构则是完全自定义的,只需要通过一个u4 长度属性去说明属性值所占用的位置即可。一个符合规则的属性表应满足如下结构:

    这里写图片描述


    1. Code属性

    Java程序方法体中的代码经过javac 编译后,最终变为字节码指令存储在Code属性内。

    (1)结构

    Code属性出现在方法表的属性集合中,但并非所有的方法表都必须存在这个属性,例如接口或抽象类中的方法就不存在。如果方法表有Code属性存在,它的结构将如下:

    这里写图片描述

    (2)结构分析

    • attribute_name_index:是一项指向CONSTANT_Utf8_info 型常量的索引,常量固定值为 “Code”,它代表了该属性的属性名称;

    • attribute_length:代表属性长度;

    • max_stack:代表操作数栈(Operand Stacks)深度的最大值;

    • max_locals:代表了局部变量表所需要的存储空间;Slot是虚拟机为局部变量分配内容所使用的最小单位,对于byte, char, flaot, int, short, boolean and returnAddress 等长度不超过32位的数据类型,每个局部变量占用1个Slot;而double 和 long 这两种64位的数据类型则需要 两个Slot来存放;

    • code_length 和 code:用来存储java 源代码编译后生成的字节码指令。code_length代表字节码长度,code用于存储 字节码指令的一系列字节流;关于code_length,需要注意的是,虽然它是一个u4类型的长度值,但虚拟机中明确限制了一个方法不允许超过65535条字节码指令,即它实际上只使用了u2的长度,如果超过这个限制, javac编译器会拒绝编译;

    • Code属性:是Class文件中最重要的一个属性,如果把一个java程序中的信息分为代码(Code,方法体里面的java代码)和元数据(metadata,包括类,字段,方法定义以及其他信息)两部分,那么在整个Class文件中,Code属性用于描述代码,所有的其他数据项目都用于描述元数据;

    (3)实例解析

    这里写图片描述

    还是以原代码为实例,可见上图,这是上一节分析过的实例构造器“”方法的Code属性。它的操作数栈的最大深度和本地变量表的容量都为0x0001,字节码区域所占空间的长度为0x0005。虚拟机读取到字节码区域的长度后,按照顺序依次读入紧随的5个字节,并根据字节码指令表翻译出所对应的字节码指令。翻译“2A B7 00 0A 01”的过程:

    • 1). 读入2A,查表得0x2A对应的指令为 aload_0,这个指令的含义是将第0个Slot中为 reference类型的本地变量推送到操作数栈顶。
    • 2). 读入B7,查表得0xB7对应的指令为 invokespecial,这条指令的作用是以栈顶的 reference类型的数据所指向的对象作为方法接收者,调用此对象的实例构造器方法、private方法或者它的父类的方法。
    • 3). 读入000A,这是invokespecial 的参数,查常量池得0x000A 对应的常量为实例构造器“”方法的符号引用。
    • 4). 读入B1,查得0xB1对应的指令为return,含义是返回此方法,并且返回值为 void。这条指令执行后,当前方法结束。

    2. Exceptions 属性

    (1)作用
    Exception属性是在方法表中与Code属性平级的一项属性,切勿与Code属性中的异常混淆。Exception属性的作用是列举出方法中可能抛出的受查异常(Checked Exception),也就是方法描述时在 throws 关键字后面列举的异常。

    (2)结构

    Exceptions 属性的结构如下表所示:

    这里写图片描述

    (3)结构解析

    number_of_exceptions:表示方法可能抛出 number_of_exceptions 种异常,每一种异常使用一个 exceptoin_index_table 项表示, exceptoin_index_table是一个指向常量池中 CONSTANT_Class_info 型常量的索引,代表了该异常类型。


    3. LineNumberTable 属性

    (1)作用

    LineNumberTable 属性用于描述java 源码行号与字节码行号的对应关系。它并不是运行时必须的属性,但默认生成到Class文件中,可以在javac中通过 -g:none 或 -g:lines 来取消或要求生成这个信息。如果选择不生成,那么当抛出异常时,堆栈中将不会显示错误的行号,且在调试程序的时候,也无法按照源码行来设置断点;

    (2)结构

    LineNumberTable 属性的结构如下表所示:

    这里写图片描述

    (3)结构解析

    line_number_table 是一个数量为 line_number_table_length,类型为 line_number_info 的集合,line_number_info 表包括了 start_pc 和 line_number 两个u2 类型的数据项,前者是字节码行号,后者是 java 源码行号。


    4. LocalVariableTable(局部参数表) 属性

    (1)作用

    LocalVariableTable 属性用于描述栈帧中局部变量表中的变量与 java 源码中定义的变量之间的关系。它并不是运行时必须的属性,但默认生成到Class文件中,可以在javac中通过使用 -g:none 或 -g:vars 来取消或要求生成这项信息;如果没有生成这项消息,最大的影响是当其他人引用这个方法时,所有的参数名称都将会丢失。

    (2)结构

    LocalVariableTable 属性的结构如下表所示:

    这里写图片描述

    其中local_variable_info项目代表了一个栈帧与源码中的局部变量的关联,结构见下表:

    这里写图片描述

    (3)结构解析

    • start_pc 和 length 属性分别代表了 这个局部变量的生命周期开始的字节码偏移量及其作用范围长度,两者结合起来就是这个局部变量在字节码中的作用域范围;

    • name_index 和 desc_index: 都是指向常量池中 CONSTANT_Utf8_info 型常量的索引,分别代表了局部变量的名称以及这个局部变量的描述符;

    • index:是这个局部变量在栈帧局部变量表中Slot的位置。当这个变量是 64 位类型时,它占用的Slot 为 index and index + 1;

    • LocalVariableTable属性:它增加了一个姐妹属性——LocalVariableTypeTable,这个新增的属性结构与LocalVariableTable 非常相似,仅仅是把记录的字段描述符的desc_index 替换为字段的特征签名,对于非泛型类型来说, 描述符和特征签名能描述的信息是基本一致的,但是泛型引入后,由于描述符中泛型的参数化类型被擦除掉,描述符就不能正确地描述泛型类型了,所以就引入了LocalVariableTypeTable了;


    5. SourceFile(记录源文件名称) 属性

    (1)作用

    SourceFile 属性用于记录生成这个Class文件的源文件名称。这个属性是可选的,默认生成,使用 javac的-g:none 或 -g:source 来关闭或生成它;如果不生成这项属性,当抛出异常时,堆栈中将不会显示出错代码所属的文件名;

    (2)结构

    SourceFile 属性的结构如下表所示:

    这里写图片描述

    (3)结构解析

    sourcefile_index:是指向常量池中CONSTANT_Utf8_info 型常量的索引,常量值是 源码文件的文件名。


    6. ConstantValue 属性

    (1)作用

    ConstantValue属性的作用是通知虚拟机自动为静态变量赋值。

    • 只有被static关键字修饰的变量才可以使用这项属性;
    • 对于非static类型的变量(实例变量),它的赋值是在实例构造器方法中进行的;
      • 在类构造器方法中;
      • 使用 ConstantValue属性;

    (2) Sun javac 编译器的选择

    目前 Sun javac 编译器的选择是:如果同时使用final 和 static 关键字来修饰一个变量,且其数据类型是基本类型或 String的话,就生成ConstantValue属性来进行初始化,如果这个变量没有被final修饰,或者并非是基本数据类型或String类型,则将会选择在 方法中进行初始化;

    (3)ConstantValue属性的定义

    jvm 规范中并没有强制要求字段必须为final,只是要求有ConstantVluae属性的字段必须设置为static而已,对final关键字的要求是 javac编译器自己加入的限制;而且对ConstantValue属性值只能限于基本类型和String,因为Class文件格式的常量类型中只有与基本属性和字符串相对应的字面量,所以ConstantValue属性不可能支持别的类型。

    (4)结构

    ConstantValue 属性的结构如下表所示:

    这里写图片描述

    (5)结构解析

    • ConstantValue属性:是一个定长属性,他的attribute_length数据项 必须为2;
    • constantvalue_index数据项:代表了常量池中一个字面量常量的引用,根据字段类型的不同 ,字面量可以是 CONSTANT_Long_info, CONSTANT_Float_info,CONSTANT_Double_info,CONSTANT_Integer_info, CONSTANT_String_info,常量中的一种;

    7. InnerClass属性

    (1)作用

    InnerClass属性用于记录内部类和宿主类间的关联。如果一个类中定义了内部类,那编译器将会为它以及它所包含的内部类生成InnerClass属性。

    (2)结构

    InnerClass属性的结构如下表所示:

    这里写图片描述

    这里写图片描述

    (3)结构分析

    数据项 number_of_classes: 代表需要记录多少个内部类信息,每个内部类的信息都由一个 inner_classes_info 表进行描述。 其结构如下:

    这里写图片描述

    • inner_class_info_index 和 outer_class_info_index :都是指向常量池中 CONSTANT_Class_info 型常量的索引,分别代表了内部类和宿主类的符号引用;
    • inner_name_index:是指向常量池中 CONSTNAT_Utf8_info 型常量的索引,代表这个内部类的名称,如果是匿名内部类,那么这项值为0;
    • inner_class_access_flags:是内部类的访问标志,它的取值范围如下所示:

    这里写图片描述


    8. Deprecated和Synthetic属性(属于标志类型的布尔属性)

    (1)定义

    Deprecated和Synthetic属性都属于标志类型的布尔属性,只存在有和没有的区别,没有属性值的概念。

    • Deprecated属性:用于表示某个类,字段或方法,已经被程序作用定为不在使用;
    • Synthetic属性:代表这个字段或方法并不是由java 源码直接产生的,而是由编译器自行添加的;

    在jdk1.5后, 标识一个类,字段或方法是编译器自动产生的,也可以设置它们访问标志中的ACC_SYNTHETIC 标志位。所有由非用户代码产生的类,方法以及字段都应该至少设置Synthetic属性和 ACC_SYNTHETIC标志位中的一项,唯一的例外就是 实例构造器 方法和类构造器 方法;

    (2)结构

    Deprecated和Synthetic属性的结构非常简单,如下表:

    这里写图片描述

    (3)结构分析

    其中 attribute_length 数据项的值必须为0x00000000,因为没有任何属性值需要设置。


    9. StackMapTable 属性

    (1)作用

    StackMapTable 属性位于Code属性的属性表中, 该属性会在虚拟机类加载的字节码验证阶段被新类型检查验证器使用, 目的在于代替以前比较消耗性能的基于数据流分析的类型推导验证器。

    (2)栈映射帧

    StackMapTable属性包含零个至多个栈映射帧(Stack Map Frames),每个栈映射帧都显式或隐式地代表了一个字节码偏移量,用于表示该执行到该字节码时局部变量表和操作数栈的验证类型。类型检查验证器会通过检查目标方法的局部变量和操作数栈所需要的类型来确定一段字节码指令是否符合逻辑约束。

    (3)结构

    Deprecated和Synthetic属性的结构非常简单,如下表:

    这里写图片描述


    10. Signature 属性

    (1)作用

    Signature 属性可以出现在类,属性表和方法表结构的属性表中。在jdk1.5 大幅增强了 java 的语法后, 任何类,接口,初始化方法或成员的泛型 签名如果包含了类型变量或参数化类型,则 Signature 属性会为它记录泛型签名信息。

    (2)引入原因

    因为java 的泛型采用的是擦除方法实现的伪泛型,在字节码(Code属性)中, 泛型信息编译之后都通通被擦除掉。擦除后的坏处就是: 运行期无法将泛型类型与用于定义的普通类型同等对待,例如运行期无法做反射时无法获得泛型信息。

    Signature属性就是为了弥补这个缺陷而增设的,现在 java的反射API能够获得泛型类型,最终的数据来源就是这个属性。

    (3)结构

    Signature 的结构如下表:

    这里写图片描述

    (4)结构分析

    signature_index 项的值必须是一个对常量池的有效索引常量池在该索引处的项必须是 CONSTANT_Utf8_info结构,表示类签名、方法类型签名或字段类型签名。


    11. BootstrapMethods 属性

    (1)作用

    BootstrapMethods 属性用于保存 invokedynamic 指令引用的引导方法限定符。

    (2)结构

    BootstrapMethods 的结构如下表:

    这里写图片描述

    (3)结构分析

    上图结构中引用到的 bootstrap_method结构见下表:

    这里写图片描述

    BootstrapMethods 属性中:

    • num_bootstrap_methods项的值给出了 bootstrap_methods[] 数组中的引导方法限定符的数量。
    • bootstrap_methods[]数组中的每个成员包含了一个指向常量池 CONSTANT_MethodHandle 结构的索引值,它代表了一个引导方法,还包含了这个引导方法静态参数的序列,数组中每个成员必须包含以下3项内容:
      • bootstrap_method_ref :它的值必须是一个对常量池的有效索引。
      • num_bootstrap_arguments:它的值给出了bootstrap_methods[]数组的成员数量。
      • bootstrap_arguments:数组的每个成员必须是一个对常量池的有效索引。



    三. 总结

    通过此篇博文与上一篇博文完成了有关Class文件存储格式的具体细节及描述的详细信息,各个不同数据项的区别于使用。解析Class文件的数据结构是这两篇文章的重点,对数据结构方面的学习难免会有些枯燥,而且底层知识学习的难度也有所增加,可能学习起来不如最初几篇博文轻易,但是还是要重复声明,这部分是了解虚拟机的重要基础之一,不可避免。


    若有错误,欢迎指教 ~

    展开全文
  • 摘要 星际文件系统是一种点点的分布式文件系统, 旨在连接所有有相同的文件系统的计算机设备。在某些方面, IPFS类似于web, 但...这形成了一个广义的Merkle DAG 数据结构,可以用这个数据结构构建版本文件系统,...

    摘要

    星际文件系统是一种点对点的分布式文件系统, 旨在连接所有有相同的文件系统的计算机设备。在某些方面, IPFS类似于web, 但web 是中心化的,而IPFS是一个单一的Bittorrent 群集, 用git 仓库分布式存储。换句话说, IPFS 提供了高吞吐量的内容寻址块存储模型, 具有内容寻址的超链接。这形成了一个广义的Merkle DAG 数据结构,可以用这个数据结构构建版本文件系统,区块链,甚至是永久性网站。。IPFS 结合了分布式哈希表, 带有激励机制的块交换和自我认证命名空间。IPFS 没有单故障点, 节点不需要相互信任。

    1. 介绍

    在全球分布式文件系统这领域, 已经有许多人的尝试。一些系统已经取得了重大的成功, 而很多却完全失败了。在学术尝试中, AFS【6】就是成功的例子,如今已经得到广泛的应用, 然而,其他的【7, ?】却没有得到相同的结果。在学术界之外,应用最广泛的是面向音视频媒体的点对点文件共享系统。 最值得注意的是, Napster, KaZaA 和BitTorrent[2]部署的文件分发系统支持1亿用户的同时在线。即使在今天, BitTorrent 也维持着每天千万节点的活跃数。 基于这些学术文件系统理论而实现的应用程序有很多的用户量, 然而,这些系统理论是在应用层,而没有放在基础层。以致没有出现通用的文件系统基础框架, 给全球提供低延迟的分发。
    也许是因为HTTP这样“足够好“的系统已经存在。到目前为止,HTTP已经作为“分布式文件系统“的协议,并且已经大量部署,再与浏览器相结合,具有巨大的技术和社会影响力。在现在, 它已经成为互联网传输文件的事实标准。然而,他没有采用最近15年的发明的数十种先进的文件分发技术。 从一方面讲, 由于向后兼容的限制 和 当前新模式的投入, 不断发展http web 的基础设施几乎是不可能的。但从一个角度看, 从http 出现以来, 已经有许多新协议出现并被广泛使用。升级http协议虽然能引入新功能和加强当前http协议,但会降低用户的体验。
    有些行业已经摆脱使用HTTP 这么久, 因为移动小文件相对便宜,即使对拥有大流量的小组织也是如此。但是,随着新的挑战,我们正在进入数据分发的新纪元。

    • (a)托管和分发PB级数据集,
    • (b)跨组织的大数据计算,
    • (c)大批量的高清晰度按需或实时媒体流,
    • (d)大规模数据集的版本化和链接,
    • (e)防止意外丢失重要文件等。其中许多可以归结为“大量数据,无处不在”。由于关键功能和带宽问题,我们已经为不同的数据放弃了HTTP 分销协议。下一步是使它们成为web自己的一部分。
      正交于有效的数据分发,版本控制系统,已经设法开发重要的数据协作工作流程。Git是分布式源代码版本控制系统,开发了许多有用的方法来建模和实现分布式数据操作。Git工具链提供了灵活的版本控制功能,这正是大量的文件分发系统所严重缺乏的。由Git启发的新解决方案正在出现,如Camlistore [?],个人文件存储系统,Dat [?]数据协作工具链和数据集包管理器。Git已经影响了分布式文件系统设计[9],因为其内容涉及到Merkle DAG数据模型,能够实现强大的文件分发策略。还有待探讨的是,这种数据结构如何影响面向高吞吐量的文件系统的设计,以及如何升级Web本身。
      本文介绍了IPFS,一种新颖的对等版本控制的文件系统,旨在调和这些问题。 IPFS综合了许多以前成功的系统的优点。 IPFS产生了突出的效果, 甚至比参考的这些系统的总和还要好。IPFS的核心原则是将所有数据建模为同一Merkle DAG的一部分。

      2. 背景

      本节回顾了IPFS所采用成功的点对点系统技术的重要属性。

      2.1 分布式哈希表(DHT)

      分布式散列表(DHT)被广泛用于协调和维护关于对等系统的元数据。比如,MainlineDHT 是一个去中心化哈希表,他可追踪查找所有的对等节点。

      2.1.1 KADEMLIA DHT

      Kademlia[10] 是受欢迎的DHT, 它提供:
    • 1.通过大量网络进行高效查询:查询平均联系人O(log2N)节点。 (例如,20跳10万个节点的网络)
    • 2.低协调开销:优化数量的控制消息发送到其他节点。
    • 3.抵抗各种攻击,喜欢长寿节点。
    • 4.在对等应用中广泛使用,包括Gnutella和BitTorrent,形成了超过2000万个节点的网络[16]。

    2.1.2 CORAL DSHT

    虽然一些对等文件系统直接在DHT中存储数据块,这种“数据存储在不需要的节点会乱费存储和带宽”[5]。Coral DSHT扩展了Kademlia三个特别重要的方式:

    • 1.Kademlia在ids为“最近”(使用XOR-distance)的关键节点中存储值。这不考 虑应用程序数据的局部性,忽略“远”可能已经拥有数据的节点,并强制“最近”节点存储它,无论它们是否需要。这浪费了大量的存储和带宽。相反,Coral 存储了地址, 该地址的对等节点可以提供相应的数据块。
    • 2.Coral将DHT API从get_value(key)换成了get_any_values(key)(DSHT中的“sloppy”)中。这仍然是因为Coral用户只需要一个(工作)的对等体,而不是完整的列表。作为回报,Coral可以仅将子集分配到“最近”的节点,避免热点(当密钥变得流行时,重载所有最近的节点)。
    • 3.另外,Coral根据区域和大小组织了一个称为群集的独立DSHT层次结构。这使得节点首先查询其区域中的对等体,“查找附近的数据而不查询远程节点”[5]并大大减少查找的延迟。

      2.1.3 S/KADEMLIA DHT

      S/Kademlia[1] 扩展了Kademlia, 用于防止恶意的攻击。有如下两方面的方法:
    • 1.S/Kad 提供了方案来保证NodeId的生成已经防止Sybill攻击。它需要节点产生PKI公私钥对。从中导出他们的身份,并彼此间签名。一个方案使用POW工作量证明,使得生成Sybills成本高昂。
    • 2.S/Kad 节点在不相交的路径上查找直, 即使网络中存在大量的不诚实节点,也能确保诚实节点可以互相链接。即使网络中存在一半的不诚实节点,S/Kad 也能达到85%的成功率。

      2.2 块交换 - BitTorrent

      BitTorrent[3] 是一个广泛成功应用的点对点共享文件系统,它可以在存在不信任的对等节点(群集)的协作网络中分发各自的文件数据片。从BitTorrent和它的生态系统的关键特征, IPFS得到启示如下:
    • 1.BitTorrent的数据交换协议使用了一种bit-for-tat的激励策略, 可以奖励对其他方面做贡献的节点,惩罚只榨取对方资源的节点。
    • 2.BitTorrent对等体跟踪文件的可用性,优先发送稀有片段。这减轻了seeds节点的负担, 让non-seeds节点有能力互相交易。
    • 3.对于一些剥削带宽共享策略, BitTorrent的标准tit-for-tat策略是非常脆弱的。 然而,PropShare[8]是一种不同的对等带宽分配策略, 可以更好的抵制剥削战略, 提高群集的表现。

      2.3. 版本控制系统- Git

      版本控制系统提供了对随时间变化的文件进行建模的设施,并有效地分发不同的版本。流行版本控制系统Git提供了强大的Merkle DAG对象模型,以分布式友好的方式捕获对文件系统树的更改。
    • 1.不可更改的对象表示文件(blob),目录(树)和更改(提交)。
    • 2.通过加密hash对象的内容,让对象可寻址。
    • 3.链接到其他对象是嵌入的,形成一个Merkle DAG。这提供了很多有用的完整和work-flow属性。
    • 4.很多版本元数据(分支,标示等等)都只是指针引用,因此创建和更新的代价都小。
    • 5.版本改变只是更新引用或者添加对象。
    • 6.分布式版本改变对其他用户而言只是转移对象和更新远程引用。

      2.4 自我认证认文件系统-SFS

      SFS [ 12,11 ]提出了两个引人注目的实现(a)分布式信任链,和(b)平等共享的全局命名空间。SFS引入了一种自我建构技术—注册文件:寻址远程文件系统使用以下格式:

       

      1

      2

      3

       

      /sfs/<Location>:<HostID>

      Location:代表的是服务网络地方

      HostID = hash(public_key || Location)

      因此SFS文件系统的名字认证了它的服务,用户可以通过服务提供的公钥来验证,协商一个共享的私钥,保证所有的通信。所有的SFS实例都共享了一个全局的命名空间,这个命名空间的名称分配是加密的,不被任何中心化的body控制。

    3. IPFS设计

    IPFS是一个分布式文件系统,它综合了以前的对等系统的成功想法,包括DHT,BitTorrent,Git和SFS。 IPFS的贡献是简化,发展和将成熟的技术连接成一个单一的内聚系统,大于其部分的总和。 IPFS提供了编写和部署应用程序的新平台,以及一个新的分发系统版本化大数据。 IPFS甚至可以演进网络本身。
    IPFS是点对点的;没有节点是特权的。 IPFS节点将IPFS对象存储在本地存储中。节点彼此连接并传输对象。这些对象表示文件和其他数据结构。 IPFS协议分为一组负责不同功能的子协议:
    1. 身份 - 管理节点身份生成和验证。描述在3.1节。
    2.网络 - 管理与其他对等体的连接,使用各种底层网络协议。可配置的。详见3.2节。
    3.路由 - 维护信息以定位特定的对等体和对象。响应本地和远程查询。默认为DH​​T,但可更换。在3.3节描述。
    4.交换 - 一种支持有效块分配的新型块交换协议(BitSwap)。模拟市场,弱化数据复制。贸易策略可替换。描述在3.4节。
    5.对象 - 具有链接的内容寻址不可更改对象的Merkle DAG。用于表示任意数据结构,例如文件层次和通信系统。详见第3.5节。
    6.文件 - 由Git启发的版本化文件系统层次结构。详见3.6节。
    7.命名 - 自我认证的可变名称系统。详见3.7节。
    这些子系统不是独立的;它们是集成在一起,互相利用各自的属性。但是,分开描述它们是有用的,从下到上构建协议栈。符号:Go语言中指定了以下数据结构和功能

    3.1 身份

    节点由NodeId标识,这是使用S / Kademlia的静态加密难题[1]创建的公钥的密码散列。节点存储其公私钥(用密码加密)。用户可以在每次启动时自由地设置一个“新”节点身份,尽管这会损失积累的网络利益。激励节点保持不变。

     

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

     

    type NodeId Multihash

    type Multihash []byte // 自描述加密哈希摘要

    type PublicKey []byte

    type PrivateKey []byte // 自描述的私钥

    type Node struct {

    NodeId NodeID

    PubKey PublicKey

    PriKey PrivateKey

    }

    基于S / Kademlia的IPFS身份生成:

    difficulty = <integer parameter>

    n = Node{}

    do {

    n.PubKey, n.PrivKey = PKI.genKeyPair()

    n.NodeId = hash(n.PubKey)

    p = count_preceding_zero_bits(hash(n.NodeId))

    } while (p < difficulty)

     

    首次连接时,对等体交换公钥,并检查:hash(other.PublicKey)等于other.NodeId。如果没有,则连接被终止
    关于加密函数的注意事项:
    IPFS不是将系统锁定到一组特定的功能选择,而是支持自我描述的值。哈希摘要值以多重哈希格式存储,其包括指定使用的哈希函数的头和以字节为单位的摘要长度。例如:

     

    1

     

    <function code><digest length><digest bytes>

     

    这允许系统

    • (a)选择最佳功能用例(例如,更强的安全性与更快的性能),
    • (b)随着功能选择的变化而演变。自描述值允许兼容使用不同的参数选择。

      3.2 网络

      IPFS节点与数百个其他节点进行定期通信网络中的节点,可能跨越广域网络。IPFS网络堆栈功能:
    • 传输层: IPFS可以使用任何传输协议,并且最适合WebRTC DataChannels [?](用于浏览器连接)或uTP(LEDBAT [14])。
    • 可靠性: 如果底层网络不提供可靠性,IPFS可使用uTP(LEDBAT [14])或SCTP [15]来提供​​可靠性。
    • 可连接性:IPFS还可以使用ICE NAT穿墙打洞技术[13]。
    • 完整性:可以使用哈希校验和来检查邮件的完整性。
    • 可验证性:可以使用发送者的公钥使用HMAC来检查消息的真实性。

      3.2.1对等节点寻址注意事项:

      IPFS可以使用任何网络; 但它不承担对IP的获取以及不直接依赖于ip层。这允许在覆盖网络中使用IPFS。
      IPFS将地址存储为多层地址,这个多层地址是由字节字符串组成的, 以便于给底层网络使用。多层地址提供了一种方式来表示地址及其协议,可以封装成好解析的格式。例如:
       

      1

      2

      3

      4

       

      # an SCTP/IPv4 connection

      /ip4/10.20.30.40/sctp/1234/

      # an SCTP/IPv4 connection proxied over TCP/IPv4

      /ip4/5.6.7.8/tcp/5678/ip4/1.2.3.4/sctp/1234/

    3.3 路由

    IPFS节点需要一个路由系统, 这个路由系统可用于查找:

    • (a)其他同伴的网络地址,
    • (b)专门用于服务特定对象的对等节点。
      IPFS使用基于S / Kademlia和Coral的DSHT,在2.1节中具体介绍过。在对象大小和使用模式方面, IPFS 类似于Coral[5] 和Mainline[16], 因此,IPFS DHT根据其大小对存储的值进行区分。小的值(等于或小于1KB)直接存储在DHT上。对于更大的值,DHT只存储值索引,这个索引就是一个对等节点的NodeId, 该对等节点可以提供對该类型的值的具体服务。
      DSHT的接口如下:
       

      1

      2

      3

      4

      5

      6

      7

       

      type IPFSRouting interface {

      FindPeer(node NodeId) // 获取特定NodeId的网络地址。

      SetValue(key []bytes, value []bytes) // 往DHT存储一个小的元数据。

      GetValue(key []bytes) // 从DHT获取元数据。

      ProvideValue(key Multihash) // 声明这个节点可一个提供一个大的数据。

      FindValuePeers(key Multihash, min int) // 获取服务于该大数据的节点。

      }

    注意:不同的用例将要求基本不同的路由系统(例如广域网中使用DHT,局域网中使用静态HT)。因此,IPFS路由系统可以根据用户的需求替换的。只要使用上面的接口就可以了,系统都能继续正常运行。

    3.4块交换 - BitSwap协议

    IPFS 中的BitSwap协议受到BitTorrent 的启发,通过对等节点间交换数据块来分发数据的。像BT一样, 每个对等节点在下载的同时不断向其他对等节点上传已下载的数据。和BT协议不同的是, BitSwap 不局限于一个torrent文件中的数据块。BitSwap 协议中存在一个永久的市场。 这个市场包括各个节点想要获取的所有块数据。而不管这些块是哪些如.torrent文件中的一部分。这些快数据可能来自文件系统中完全不相关的文件。 这个市场是由所有的节点组成的。
    虽然易货系统的概念意味着可以创建虚拟货币,但这将需要一个全局分类账本来跟踪货币的所有权和转移。这可以实施为BitSwap策略,并将在未来的论文中探讨。
    在基本情况下,BitSwap节点必须以块的形式彼此提供直接的值。只有当跨节点的块的分布是互补的时候,各取所需的时候,这才会工作的很好。 通常情况并非如此,在某些情况下,节点必须为自己的块而工作。 在节点没有其对等节点所需的(或根本没有的)情况下,它会更低的优先级去寻找对等节点想要的块。这会激励节点去缓存和传播稀有片段, 即使节点对这些片段不感兴趣。

    3.4.1 - BITSWAP 信用

    这个协议必须带有激励机制, 去激励节点去seed 其他节点所需要的块,而它们本身是不需要这些块的。 因此, BitSwap的节点很积极去给对端节点发送块,期待获得报酬。但必须防止水蛭攻击(空负载节点从不共享块),一个简单的类似信用的系统解决了这些问题:

    • 1, 对等节点间会追踪他们的平衡(通过字节认证的方式)。
    • 2, 随着债务增加而概率降低,对等者概率的向债务人发送块。
      注意的是,如果节点决定不发送到对等体,节点随后忽略对等体的ignore_cooldown超时。 这样可以防止发送者尝试多次发送(洪水攻击) (BitSwap默认是10秒)。

      3.4.2 BITSWAP的策略

      BitSwap 对等节点采用很多不同的策略,这些策略对整个数据块的交换执行力产生了不同的巨大影响。在BT 中, 标准策略是明确规定的(tit-for-tat),其他不同的策略也已经被实施,从BitTyrant [8](尽可能分享)到BitThief [8](利用一个漏洞,从不共享),到PropShare [8](按比例分享)。BitSwap 对等体可以类似地实现一系列的策略(良好和恶意)。对于功能的选择,应该瞄准:
    • 1.为整个交易和节点最大化交易能力。
    • 2.为了防止空负载节点利用和损害交易。
    • 3.高效抵制未知策略。
    • 4.对可信任的对等节点更宽容。
      探索这些策略的空白是未来的事情。在实践中使用的一个选择性功能是sigmoid,根据负债比例进行缩放:
      让负债比例在一个节点和它对等节点之间:
       

      1

       

      r = bytes_sent / bytes_recv + 1

    根据r,发送到负债节点的概率为:

     

    1

     

    P(send | r ) = 1 − ( 1/ ( 1 + exp(6 − 3r) ) )

     

    正如你看到的图片1,当节点负债比例超过节点已建立信贷的两倍,发送到负债节点的概率就会急速下降。

    图片1  当r增加时发送的概率
    

    负债比是信任的衡量标准:对于之前成功的互换过很多数据的节点会宽容债务,而对不信任不了解的节点会严格很多。这个(a)给与那些创造很多节点的攻击者(sybill 攻击)一个障碍。(b)保护了之前成功交易节点之间的关系,即使这个节点暂时无法提供数据。(c)最终阻塞那些关系已经恶化的节点之间的通信,直到他们被再次证明。

    3.4.3 BITSWAP 账本

    BitSwap节点保存了一个记录与所有其他节点之间交易的账本。这个可以让节点追踪历史记录以及避免被篡改。当激活了一个链接,BitSwap节点就会互换它们账本信息。如果这些账本信息并不完全相同,分类账本将会重新初始化, 那些应计信贷和债务会丢失。 恶意节点会有意去失去“这些“账本, 从而期望清除自己的债务。节点是不太可能在失去了应计信托的情况下还能累积足够的债务去授权认证。伙伴节点可以自由的将其视为不当行为, 拒绝交易。

     

    1

    2

    3

    4

    5

    6

    7

     

    type Ledger struct {

    owner NodeId

    partner NodeId

    bytes_sent int

    bytes_recv int

    timestamp Timestamp

    }

     

    节点可以自由的保留分布式账本历史,这不需要正确的操作,因为只有当前的分类账本条目是有用的。节点也可以根据需要自由收集分布式帐本,从不太有用的分布式帐开始:老(其他对等节点可能不存在)和小。

    3.4.4 BITSWAP 详解

    BitSwap 节点有以下简单的协议。

     

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    16

    17

    18

    19

    20

    21

     

    // Additional state kept

    type BitSwap struct {

    ledgers map[NodeId]Ledger // Ledgers known to this node, inc inactive

    active map[NodeId]Peer // currently open connections to other nodes

    need_list []Multihash // checksums of blocks this node needs

    have_list []Multihash // checksums of blocks this node has

    }

    type Peer struct {

    nodeid NodeId

    ledger Ledger // Ledger between the node and this peer

    last_seen Timestamp // timestamp of last received message

    want_list []Multihash // checksums of all blocks wanted by peer

    // includes blocks wanted by peer's peers

    }

    // Protocol interface:

    interface Peer {

    open (nodeid : NodeId, ledger : Ledger);

    send_want_list (want_list : WantList);

    send_block(block: Block) -> (complete:Bool);

    close(final: Bool);

    }

     

    对等连接的生命周期草图:

    • 1.Open: 对等节点间发送ledgers 直到他们同意。
    • 2.Sending: 对等节点间交换want_lists 和blocks。
    • 3.Close: 对等节点断开链接。
    • 4.Ignored: (特殊)对等体被忽略(等待时间的超时)如果节点采用防止发送策略。
      Peer.open(NodeId, Ledger).
      当发生链接的时候,节点会初始化链接的账本,要么保存一个份链接过去的账本,要么创建一个新的被清零的账本。然后,发送一个携带账本的open信息给对等节点。
      接收到一个open信息之后,对等节点可以选择是否接受此链接。如果,根据接收者的账本,发送者是一个不可信的代理(传输低于零或者有很大的未偿还的债务),接收者可能会选择忽略这个请求。忽略请求是ignore_cooldown超时来概率性实现的,为了让错误能够有时间改正和攻击者被挫败。
      如果链接成功,接收者用本地账本来初始化一个Peer对象以及设置last_seen时间戳。然后,它会将接受到的账本与自己的账本进行比较。如果两个账本完全一样,那么这个链接就被Open,如果账本并不完全一致,那么此节点会创建一个新的被清零的账本并且会发送此账本。
      Peer.send_want_list(WantList)
      当链接已经Open的时候,节点会广发它们的want_list给所有已经链接的对等节点。这个是在(a)open链接后(b)随机间歇超时后(c)want_list改变后(d)接收到一个新的块之后完成的。
      当接收到一个want_list之后,节点会存储它。然后,会检查自己是否拥有任何它想要的块。如果有,会根据上面提到的BitSwap策略来将want_list所需要的块发送出去。
      Peer.send_block(Block)
      发送一个块是直接了当的。节点只是传输数据块。当接收到了所有数据的时候,接收者会计算多重hash校验和来验证它是否是自己所需数据,然后发送确认信息。
      在完成一个正确的块传输之后,接受者会将此块从need_list一到have_list,最后接收者和发送者都会更新它们的账本来反映出传输的额外数据字节数。
      如果一个传输验证失败了,发送者要么会出故障要么会攻击接收者,接收者可以选择拒绝后面的交易。注意,BitSwap是期望能够在一个可靠的传输通道上进行操作的,所以传输错误(可能会引起一个对诚实发送者错误的惩罚)是期望在数据发送给BitSwap之前能够被捕捉到。
      Peer.close(Bool)
      传给close最后的一个参数,代表close链接是否是发送者的意愿。如果参数值为false,接收者可能会立即重新open链接,这避免链过早的close链接。
      一个对等节点close链接发生在下面两种情况下:
    • silence_wait超时已经过期,并且没有接收到来自于对等节点的任何信息(BitSwap默认使用30秒),节点会发送Peer.close(false)。
    • 在节点退出和BitSwap关闭的时候,节点会发送Peer.close(true).
      接收到close消息之后,接收者和发送者会断开链接,清除所有被存储的状态。账本可能会被保存下来为了以后的便利,当然,只有在被认为账本以后会有用时才会被保存下来。
      注意点:
      非open信息在一个不活跃的连接上应该是被忽略的。在发送send_block信息时,接收者应该检查这个块,看它是否是自己所需的,并且是否是正确的,如果是,就使用此块。总之,所有不规则的信息都会让接收者触发一个close(false)信息并且强制性的重初始化此链接。

      3.5 Merkle DAG对象

      DHT和BitSwap允许IPFS构造一个庞大的点对点系统用来快速稳定的分发和存储。最主要的是,IPFS建造了一个Merkle DAG,一个无回路有向图,对象之间的links都是hash加密嵌入在源目标中。这是Git数据结构的一种推广。Merkle DAGS给IPFS提供了很多有用的属性,包括:
    • 1.内容可寻址:所有内容都是被多重hash校验和来唯一识别的,包括links。
    • 2.防止篡改:所有的内容都用它的校验和来验证。如果数据被篡改或损坏,IPFS会检测到。
    • 3.重复数据删除:所有的对象都拥有相同的内容并只存储一次。这对于索引对象非常有用,比如git的tree和commits,或者数据的公共部分。

    IPFS对象的格式是:

     

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

     

    type IPFSLink struct {

    Name string // 此link的别名

    Hash Multihash // 目标的加密hash

    Size int // 目标总大小

    }

    type IPFSObject struct {

    links []IPFSLink //links数组

    data []byte //不透明内容数据

    }

     

    IPFS Merkle DAG是存储数据非常灵活的一种方式。只要求对象引用是(a)内容可寻址的,(b)用上面的格式编码。IPFS允许应用完全的掌控数据域;应用可以使用任何自定义格式的数据,即使数据IPFS都无法理解。单独的内部对象link表允许IPFS做:

    • 用对象的形式列出所有对象引用,例如:
       

      1

      2

      3

      4

      5

      6

       

      > ipfs ls /XLZ1625Jjn7SubMDgEyeaynFuR84ginqvzb

      XLYkgq61DYaQ8NhkcqyU7rLcnSa7dSHQ16x 189458 less

      XLHBNmRQ5sJJrdMPuu48pzeyTtRo39tNDR5 19441 script

      XLF4hwVHsVuZ78FZK6fozf8Jj9WEURMbCX4 5286 template

      <object multihash> <object size> <link name>

    • 解决字符串路经查找,例如foo/bar/baz。给出一个对象,IPFS会解析第一个路经成分进行hash放入到对象的link表中,再获取路径的第二个组成部分,一直如此重复下去。因此,任何数据格式的字符串路经都可以在Merkle DAG中使用。
      *递归性的解决所有对象引用:
       

      1

      2

      3

      4

      5

      6

       

      > ipfs refs --recursive \

      /XLZ1625Jjn7SubMDgEyeaynFuR84ginqvzb

      XLLxhdgJcXzLbtsLRL1twCHA2NrURp4H38s

      XLYkgq61DYaQ8NhkcqyU7rLcnSa7dSHQ16x

      XLHBNmRQ5sJJrdMPuu48pzeyTtRo39tNDR5

      XLWVQDqxo9Km9zLyquoC9gAP8CL1gWnHZ7z

    原始数据结构公共link结构是IPFS构建任意数据结构的必要组成部分。可以很容易看出Git的对象模型是如何套用DAG的。一些其他潜在的数据结构:

    • (a)键值存储
    • (b)传统关系型数据
    • (c)数据三倍存储
    • (d) 文档发布系统
    • (e)通信平台
    • (f)加密货币区块。
      这些系统都可以套用IPFS Merkle DAG,这使这些系统更复杂的应用可以使用IPFS作为传输协议。

    3.5.1 路经

    IPFS对象可以遍历一个字符串路经。路经格式与传统UNIX文件系统以及Web一致。Merkle DAG的links使遍历变得很容易。全称路经在IPFS中的格式是:

     

    1

    2

    3

    4

     

    *# 格式

    /ipfs/<hash-of-object>/<name-path-to-object>

    *# 例子

    /ipfs/XLYkgq61DYaQ8NhkcqyU7rLcnSa7dSHQ16x/foo.txt

     

    /ipfs前缀允许只要在挂载点不冲突(挂载点名称当然是可配置的)的情况下挂载到一个已存在的系统上。第二个路经组成部分(第一个是IPFS)是一个对象的hash。通常都是这种情况,因为没有全局的根。一个根对象可能会有一个不可能完成的任务,就是在分布式环境(可能还断开链接)中处理百万对象的一致性。因此,我们用地址可寻址来模拟根。通过的hash所有的对象都是可访问的。这意思是说,给一个路经对象/bar/baz,最后一个对象可以可以被所有的访问的:

     

    1

    2

    3

     

    /ipfs/<hash-of-foo>/bar/baz

    /ipfs/<hash-of-bar>/baz

    /ipfs/<hash-of-baz>

     

    3.5.2 本地对象

    IPFS客户端需要一个本地存储器,一个外部系统可以为IPFS管理的对象存储以及检索本地原始数据。存储器的类型根据节点使用案例不同而不同。在大多数情况下,这个存储器只是硬盘空间的一部分(不是被本地的文件系统使用键值存储如leveldb来管理,就是直接被IPFS客户端管理),在其他的情况下,例如非持久性缓存,存储器就是RAM的一部分。
    最终,所有的块在IPFS中都是能够获取的到的,块都存储在了一些节点的本地存储器中。当用户请求一个对象时,这个对象会被查找到并下载下来存储到本地,至少也是暂时的存储在本地。这为一些可配置时间量提供了快速的查找。

    3.5.3对象锁定

    希望确保特定对象生存的节点可以锁定此对象。这保证此特定对象被保存在了节点的本地存储器上。也可以递归的进行锁定所有相关的派生对象。这使所有被指定的对象都保存在本地存储器上。这对长久保存文件特别有用,包括引用。这也同样让IPFS成为一个links是永久的Web,且对象可以确保其他被指定对象的生存。

    3.5.4 发布对象

    IPFS是全球分布的。它设计为允许成千上万的用户文件可以共同的存在的。DHT使用内容哈希寻址技术,使发布对象是公平的,安全的,完全分布式的。任何人都可以发布对象,只需要将对象的key加入到DHT中,并且以对象是对等节点的方式加入进去,然后把路径给其他的用户。要注意的是,对象本质上是不可改变的,就像在Git中一样。新版本的哈希值不同,因此是新对象。跟踪版本则是额外版本对象的工作。

    3.5.5 对象级别的加密

    IPFS是具备可以处理对象级别加密操作的。一个已加密的或者已签名的对象包装在一个特殊的框架里,此框架允许加密和验证原始字节。

     

    1

    2

    3

    4

    5

    6

    7

    8

     

    type EncryptedObject struct {

    Object []bytes // 已加密的原始对象数据

    Tag []bytes // 可选择的加密标识

    type SignedObject struct {

    Object []bytes // 已签名的原始对象数据

    Signature []bytes // HMAC签名

    PublicKey []multihash // 多重哈希身份键值

    }

     

    加密操作改变了对象的哈希值,定义一个不同的新的对象。IPFS自动的验证签名以及使用用户指定的钥匙链解密数据。加密数据的links也同样的被保护着,没有解密秘钥就无法遍历对象。也存在着一种现象,可能父对象使用了一个秘钥进行了加密,而子对象使用了另一个秘钥进行加密或者根本没有加密。这可以保证links共享对象安全。

    3.6 文件

    IPFS在Merkle DAG上还为模型化版本文件系统定义了一组对象。这个对象模型与Git比较相似:
    Block:一个可变大小的数据块
    List:块或者其他链表的集合
    Tree:块,链表,或者其他树的集合
    Commit:树在版本历史记录中的一个快照
    我原本希望使用与Git对象格式一致的模型,但那就必须要分开来引进在分布式文件系统中有用的某些特征,如

    • (a)快速大小查找(总字节大小已经加入到对象中)
    • (b)大文件的重复删除(添加到list对象)
    • (c)commits嵌入到trees中。不过,IPFS文件对象与Git还是非常相近的,两者之间进行交流都是有可能的。而且,Git的一个系列的对象可以被引进过来转换都不会丢失任何的信息。(UNIX文件权限等等)。
      标记:下面的文件对象格式使用JSON。注意,虽然IPFS包含了JSON的互相转换,但是文件对象的结构体还是使用protobufs的二进制编码。

      3.6.1 文件对象:BLOB

      blob对象代表一个文件且包含一个可寻址的数据单元,IPFS的blobs就像Git的blobs或者文件系统数据块。它们存储用户的数据。需要留意的是IPFS文件可以使用lists或者blobs来表示。Blobs没有links。
       

      1

      2

      3

       

      {

      "data": "some data here", // blobs无links

      }

    3.6.2 文件对象: LIST

    List对象代表着由几个IPFS的blobs连接成的大文件或者重复数据删除文件。Lists包含着有序的blob序列或list对象。从某种程度上而言,IPFS的list函数就像一个间接块的文件系统。由于lists可以包含其他的lists,那么包含linked的链表和平衡树的拓扑结构是有可能的。有向图中相同的节点出现在多个不同地方允许在文件中重复数据删除。当然,循环是不可以能的,因为是被哈希寻址强制实行的。

     

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

     

    {

    "data": ["blob", "list", "blob"], //lists有一个对象类型的数组作为数据

    "links": [

    { "hash": "XLYkgq61DYaQ8NhkcqyU7rLcnSa7dSHQ16x",

    "size": 189458 },

    { "hash": "XLHBNmRQ5sJJrdMPuu48pzeyTtRo39tNDR5",

    "size": 19441 },

    { "hash": "XLWVQDqxo9Km9zLyquoC9gAP8CL1gWnHZ7z",

    "size": 5286 } //在links中lists是没有名字的

    ]

    }

     

    3.6.3 文件对象:TREE

    IPFS中的tree对象与Git中相似,它代表着一个目录,一个名字到哈希值的映射。哈希值则表示着blobs,lists,其他的trees,或者commits。注意,传统路径的命名早已经被Merkle DAG实现了。

     

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

     

    {

    "data": ["blob", "list", "blob"],//trees有一个对象类型的数组作为数据

    "links": [

    { "hash": "XLYkgq61DYaQ8NhkcqyU7rLcnSa7dSHQ16x",

    "name": "less", "size": 189458 },

    { "hash": "XLHBNmRQ5sJJrdMPuu48pzeyTtRo39tNDR5",

    "name": "script", "size": 19441 },

    { "hash": "XLWVQDqxo9Km9zLyquoC9gAP8CL1gWnHZ7z",

    "name": "template", "size": 5286 }//trees是有名字的

    ]

    }

     

    3.6.4 文件对象:COMMIT

    IPFS中的commit对象代表任何对象在版本历史记录中的一个快照。与Git中类似,但是它能够表示任何类型的对象。它同样link着发起对象。

    3.6.5 版本控制

    Commit对象代表着一个对象在历史版本中的一个特定快照。在两个不同的commit中比较对象(和子对象)可以揭露出两个不同版本文件系统的区别。只要commit和它所有子对象的引用是能够被访问的,所有前版本是可获取的,所有文件系统改变的全部历史是可访问的,这就与Merkle DAG对象模型脱离开来了。

    Git版本控制工具的所有功能对于IPFS的用户是可用的。对象模型不完全一致,但也是可兼容的。这可能

    • (a)构建一个Git工具版本改造成使用IPFS对象图,
    • (b)构建一个挂载FUSE文件系统,挂载一个IPFS的tree作为Git的仓库,把Git文件系统的读/写转换为IPFS的格式。

      3.6.6 文件系统路径

      如我们在Merkle DAG中看到的一样,IPFS对象可以使用字符串路径API来遍历。IPFS文件对象是特意设计的,为了让挂载IPFS到UNIX文件系统更加简单。文件对象限制trees没有数据,为了使它们可以表示目录。Commits可以以代表目录的形式出现,也可以完全的隐藏在文件系统中。

    3.6.7 将文件分隔成LISTS和BLOBS

    版本控制和分发大文件其中一个最主要的挑战是:找到一个正确的方法来将它们分隔成独立的块。与其认为IPFS可以为每个不同类型的文件提供正确的分隔方法,不如说IPFS提供了以下的几个可选选择:
    就像在LIBFS[?]中一样使用Rabin Fingerprints [?]来选择一个比较合适的块边界。
    使用rsync[?] rolling-checksum算法,来检测块在版本之间的改变。
    允许用户指定专为特定文件而调整的’快分隔’函数。

    3.6.8路径查找性能

    基于路径的访问需要遍历对象图。获取每个对象要求在DHT中查找它们的key,连接到对等节点,然后获取它的块。这造成相当大的开销,特别是查找的路径由很多子路径组成时。下面的方法可以减缓开销:

    • tree缓存:由于所有的对象都是哈希寻址的,它们可以被无限的缓存。另外,trees一般比较小,所以比起blobs,IPFS会优先缓存trees。
    • flattened trees:对于任何tree,一个特殊的 flattened tree可以构建一个链表,所有对象都可以从这个tree中访问得到。在flattened tree中名字就是一个从原始tree分离的路径,用斜线分隔。
      例如,对于上面的ttt111的flattened tree如下:
       

      1

      2

      3

      4

      5

      6

      7

      8

      9

      10

      11

      12

      13

      14

      15

      16

      17

       

      {

      "data":

      ["tree", "blob", "tree", "list", "blob" "blob"],

      "links": [

      { "hash": "<ttt222-hash>", "size": 1234

      "name": "ttt222-name" },

      { "hash": "<bbb111-hash>", "size": 123,

      "name": "ttt222-name/bbb111-name" },

      { "hash": "<ttt333-hash>", "size": 3456,

      "name": "ttt333-name" },

      { "hash": "<lll111-hash>", "size": 587,

      "name": "ttt333-name/lll111-name"},

      { "hash": "<bbb222-hash>", "size": 22,

      "name": "ttt333-name/lll111-name/bbb222-name" },

      { "hash": "<bbb222-hash>", "size": 22

      "name": "bbb222-name" }

      ] }

    3.7 IPNS:命名以及易变状态

    目前为止,IPFS桟形成了一个对等块交换组成一个内容可寻址的DAG对象。这提供了发布和获取不可改变的对象。这甚至可以跟踪这些对象的版本历史记录。但是,这里有一个关键成分遗漏了:易变的命名。没有这个,发送IPFS的links,所有新内容的通信肯定都会有所偏差。现在所需就是能有某些方法可以获取相同路径的的易变状态。
    这值得详述原因—如果最终易变数据是必须的—我们费了很大的力气构建了一个不可改变的Merkle DAG。就当做IPFS脱离了Merkle DAG的特征:对象可以

    • (a)通过哈希值可以获取
    • (b)完整性的检查
    • (c)link其他的对象
    • (d)无限缓存。从某种意义上说:
      对象就是永恒的
      这些就是一个高性能分布式系统的关键特征,在此系统上跨网络links之间移动文件是非常昂贵的。对象内容可寻址构建了一个具有以下特点的Web,(a)优秀的宽带优化(b)不受信任的内容服务(c)永恒的links(d)能够永久备任何对象以及它的引用。

    不可变的内容可寻址对象和命名的Merkle DAG, 可变指针指向Merkle DAG,实例化了一个出现在很多成功分布式系统中的二分法。这些系统包括Git的版本控制系统,使用不可变的对象和可变的引用;还有UNIX分布式的继承者Plan9[?]文件系统,使用可变的Fossil和不可变的Venti[?]。LBFS[?]同样使用可变的索引以及不可变的块。

    3.7.1 自我认证名称

    使用SFS[12,11]中的命名方案,给我们提供了一个种可以构建自我认证名称的方法,
    在一个加密指定的全局命名空间中,这是可变的。IPFS的方案如下:

    • 1.回想一下在IPFS中:NodeId = hash(node.PubKey)
    • 2.我们给每个用户分配一个可变的命名空间,在此路径下:/ipns/
    • 3.一个用户可以在此路径下发布一个用自己私钥签名的对象,比如说:/ipns/XLF2ipQ4jD3UdeX5xp1KBgeHRhemUtaA8Vm/
    • 4.当其他用户获取对象时,他们可以检测签名是否与公钥和NodeId匹配。这个验证了用户发布对象的真实性,达到了可变状态的获取。

    注意下面的细节:

    • IPNS(InterPlanetary的命名空间)分开前缀是在可变和不可变的路径之间建立一个很容易辨认的区别,为了程序也为了人类阅读的便利。
    • 因为这不是一个内容可寻址的对象,所以发布它就要依靠IPFS中的唯一的可变状态分配制度,路由系统。过程是(a)首先把此对象做一个常规的不可变IPFS的对象来发布(b)将此对象的哈希值作为元数据的值发布到路由系统上:

       

      1

       

      routing.setValue(NodeId, <ns-object-hash>)

    • 发布的对象中任何links在命令空间中充当子名称:

       

      1

      2

      3

       

      /ipns/XLF2ipQ4jD3UdeX5xp1KBgeHRhemUtaA8Vm/

      /ipns/XLF2ipQ4jD3UdeX5xp1KBgeHRhemUtaA8Vm/docs

      /ipns/XLF2ipQ4jD3UdeX5xp1KBgeHRhemUtaA8Vm/docs/ipfs

    • 一般建议发布一个commit对象或者其他对象的时候,要使用历史版本记录,因为这样就用户就可以找到之前使用过的名字。不过由于这并不总是需要的,所以留个用户自己选择。
      注意当用户发布一个对象的时候,他不能使用相同的方式来发布对象。

    3.7.2人类友好名称

    IPNS的确是一个分配和在分配名称的好方法,但是对用户却不是十分友好的,因为它使用很长的哈希值作为名称,众所周知这样的名称很难被记住。IPNS足够应付URLs,但对于很多线下的传输工作就没有这么好用了。因此,IPFS使用下面的技术来增加IPNS的用户友好度。
    对等节点Links
    被SFS所鼓舞,用户可以直接将其他用户的对象link到自己的对象上(命令空间,家目录等等)。这有一个好处就是创建了一个可信任的Web(也支持老的真实性认证模型):

     

    1

    2

    3

    4

    5

    6

    7

    8

     

    # Alice links 到Bob上

    ipfs link /<alice-pk-hash>/friends/bob /<bob-pk-hash>

    # Eve links 到Alice上

    ipfs link /<eve-pk-hash/friends/alice /<alice-pk-hash>

    # Eve 也可以访问Bob

    /<eve-pk-hash/friends/alice/friends/bob

    # 访问Verisign 认证域

    /<verisign-pk-hash>/foo.com

     

    DNS TXT IPNS 记录
    如果/ipns/是一个有效的域名称,IPFS会在DNS TXT记录中查找关键的ipns。IPFS会将查找到的值翻译为一个对象的哈希值或者另一个ipns的路径:

     

    1

    2

    3

    4

     

    # DNS TXT 记录

    ipfs.benet.ai. TXT "ipfs=XLF2ipQ4jD3U ..."

    # 表现为符号链接

    ln -s /ipns/XLF2ipQ4jD3U /ipns/fs.benet.ai

     

    Proquint 可读的标识符
    总是会有将二进制编码翻译成可读文件的方法。IPNS则支持Proquint[?].。如下:

     

    1

    2

    3

    4

     

    # proquint语句

    /ipns/dahih-dolij-sozuk-vosah-luvar-fuluh

    # 分解为相应的下面形式

    /ipns/KhAwNprxYVxKqpDZ

     

    缩短名称服务
    会涌现出很多服务器提供缩短名称的服务,向用户提供他们的命名空间。就像我们现在看到的DNS和Web的URLs:

     

    1

    2

    3

    4

     

    # 用户可以从下面获取一个link

    /ipns/shorten.er/foobar

    # 然后放到自己的命名空间

    /ipns/XLF2ipQ4jD3UdeX5xp1KBgeHRhemUtaA8Vm

     

    3.8使用IPFS

    IPFS设计为可以使用多种不同的方法来使用的,下面就是一些我将会继续追求的使用方式:

    • 1.作为一个挂载的全局文件系统,挂载在/ipfs和/ipns下
    • 2.作为一个挂载的个人同步文件夹,自动的进行版本管理,发布,以及备份任何的写入
    • 3.作为一个加密的文件或者数据共享系统
    • 4.作为所有软件的版本包管理者
    • 5.作为虚拟机器的根文件系统
    • 6.作为VM的启动文件系统 (在管理程序下)
    • 7.作为一个数据库:应用可以直接将数据写入Merkle DAG数据模型中,获取所有的版本,缓冲,以及IPFS提供的分配
    • 8.作为一个linked(和加密的)通信平台
    • 9.作为一个为大文件的完整性检查CDN(不使用SSL的情况下)
    • 10.作为一个加密的CDN
    • 11.在网页上,作为一个web CDN
    • 12.作为一个links永远存在新的永恒的Web
      IPFS实现的目标:
    • (a)一个IPFS库可以导出到你自己应用中使用
    • (b)命令行工具可以直接操作对象
    • (c)使用FUSE[?]或者内核的模型挂载文件系统

      4. 未来

      IPFS的思想是几十年成功的分布式系统的探索和开源的产物。IPFS综合了很多迄今为止很成功的系统中优秀的思想。除了BitSwap新协议之外,IPFS最大的特色就是系统的耦合以及设计的综合性。
      IPFS是去中心化网络基础设施的一个野心设想,很多不同类型的应用都可以建立在IPFS上。最低限度,它可以用来作为一个全局的,挂载性,版本控制文件系统和命名空间,或者作为下一代的文件共享系统。而最好的情况是,IPFS可以让Web升级一个层次,当发布一个有价值的信息时,任何感兴趣的人都可以进行发布而不会强迫性的必须只允许发布机构进行发布,用户可以信任信息的内容,信不信任信息的发送者都是无关紧要的,还有一个特点就是,一些重要但很老的文件也不会丢失。IPFS期待着带我们进入到一个永恒Wdb的世界。

      5. 感谢

      IPFS是一个很多很棒的主意以及系统的综合体。没有站在巨人的肩膀上,IPFS也不可能敢于有一个这么有野心的目标。个人感谢参与这些主意长期讨论的人:David Dalrymple, Joe Zimmerman, and Ali Yahya,特别是:揭开Merkle DAG的总体架构(David, Joe),滚动哈希阻塞(David), s/kademlia sybill 保护(David, Ali),特别感谢David Mazieres,为他之前非常聪明的主意。

      6.引用备忘录

      7.引用

      [1].I. Baumgart and S. Mies. S/kademlia:一个安全的基于秘钥路由的可行方法。2007年国际会议,第2卷,1-8页,在《并发和分布式系统》中。IEEE,2007年。
      [2].I. BitTorrent.Bittorrent和Attorrent软件超过1亿5000万用户里程碑,Jan。2012
      [3].B. Cohen.激励机制在bittorrent中建立了健壮性。在《对等系统经济研讨会》中,第6卷,68-72页,2003年。
      [4].J. Dean and S. Ghemawat. Leveldb - 一个快速和轻量级键值存储数据库,谷歌提供,2011年。
      [5].M. J. Freedman, E. Freudenthal, and D. Mazieres. Coral民主内容发布。在NSDI中,第4卷,18-18页,2004年。
      [6].J. H. Howard, M. L. Kazar, S. G. Menees, D. A,Nichols, M. Satyanarayanan, R. N. Sidebotham, 以及M. J. West.分布式文件系统的规模和性能。“ACM 电脑系统上的交易 (TOCS)” 6(1):51-81, 1988年
    展开全文
  • mysql索引详解

    万次阅读 多人点赞 2021-07-07 21:40:09
    一个文件的名字以的名字开始,扩展名指出文件类型。.frm文件存储定义。数据文件的扩展名为.MYD (MYData)。索引文件的扩展名是.MYI (MYIndex)。 InnoDB:所有的都保存在同一个数据文件中(也可能是多个

    🍅 Java学习路线:搬砖工逆袭Java架构师

    🍅 简介:Java领域优质创作者🏆、CSDN哪吒公众号作者✌ 、Java架构师奋斗者💪

    🍅 扫描主页左侧二维码,加入群聊,一起学习、一起进步 

    🍅 欢迎点赞 👍 收藏 ⭐留言 📝  

    一、MySQL三层逻辑架构

    MySQL的存储引擎架构将查询处理与数据的存储/提取相分离。下面是MySQL的逻辑架构图:

    1、第一层负责连接管理、授权认证、安全等等。

    每个客户端的连接都对应着服务器上的一个线程。服务器上维护了一个线程池,避免为每个连接都创建销毁一个线程。当客户端连接到MySQL服务器时,服务器对其进行认证。可以通过用户名和密码的方式进行认证,也可以通过SSL证书进行认证。登录认证通过后,服务器还会验证该客户端是否有执行某个查询的权限。

    2、第二层负责解析查询

    编译SQL,并对其进行优化(如调整表的读取顺序,选择合适的索引等)。对于SELECT语句,在解析查询前,服务器会先检查查询缓存,如果能在其中找到对应的查询结果,则无需再进行查询解析、优化等过程,直接返回查询结果。存储过程、触发器、视图等都在这一层实现。

    3、第三层是存储引擎

    存储引擎负责在MySQL中存储数据、提取数据、开启一个事务等等。存储引擎通过API与上层进行通信,这些API屏蔽了不同存储引擎之间的差异,使得这些差异对上层查询过程透明。存储引擎不会去解析SQL。

    二、对比InnoDB与MyISAM

    1、 存储结构

    MyISAM:每个MyISAM在磁盘上存储成三个文件。分别为:表定义文件、数据文件、索引文件。第一个文件的名字以表的名字开始,扩展名指出文件类型。.frm文件存储表定义。数据文件的扩展名为.MYD (MYData)。索引文件的扩展名是.MYI (MYIndex)。

    InnoDB:所有的表都保存在同一个数据文件中(也可能是多个文件,或者是独立的表空间文件),InnoDB表的大小只受限于操作系统文件的大小,一般为2GB。

    2、 存储空间

    MyISAM: MyISAM支持支持三种不同的存储格式:静态表(默认,但是注意数据末尾不能有空格,会被去掉)、动态表、压缩表。当表在创建之后并导入数据之后,不会再进行修改操作,可以使用压缩表,极大的减少磁盘的空间占用。

    InnoDB: 需要更多的内存和存储,它会在主内存中建立其专用的缓冲池用于高速缓冲数据和索引。

    3、 可移植性、备份及恢复

    MyISAM:数据是以文件的形式存储,所以在跨平台的数据转移中会很方便。在备份和恢复时可单独针对某个表进行操作。

    InnoDB:免费的方案可以是拷贝数据文件、备份 binlog,或者用 mysqldump,在数据量达到几十G的时候就相对痛苦了。

    4、 事务支持

    MyISAM:强调的是性能,每次查询具有原子性,其执行数度比InnoDB类型更快,但是不提供事务支持。

    InnoDB:提供事务支持事务,外部键等高级数据库功能。 具有事务(commit)、回滚(rollback)和崩溃修复能力(crash recovery capabilities)的事务安全(transaction-safe (ACID compliant))型表。

    5、 AUTO_INCREMENT

    MyISAM:可以和其他字段一起建立联合索引。引擎的自动增长列必须是索引,如果是组合索引,自动增长可以不是第一列,他可以根据前面几列进行排序后递增。

    InnoDB:InnoDB中必须包含只有该字段的索引。引擎的自动增长列必须是索引,如果是组合索引也必须是组合索引的第一列。

    6、 表锁差异

    MyISAM: 只支持表级锁,用户在操作myisam表时,select,update,delete,insert语句都会给表自动加锁,如果加锁以后的表满足insert并发的情况下,可以在表的尾部插入新的数据。

    InnoDB: 支持事务和行级锁,是innodb的最大特色。行锁大幅度提高了多用户并发操作的新能。但是InnoDB的行锁,只是在WHERE的主键是有效的,非主键的WHERE都会锁全表的。

    7、 全文索引

    MyISAM:支持 FULLTEXT类型的全文索引

    InnoDB:不支持FULLTEXT类型的全文索引,但是innodb可以使用sphinx插件支持全文索引,并且效果更好。

    8、表主键

    MyISAM:允许没有任何索引和主键的表存在,索引都是保存行的地址。

    InnoDB:如果没有设定主键或者非空唯一索引,就会自动生成一个6字节的主键(用户不可见),数据是主索引的一部分,附加索引保存的是主索引的值。

    9、表的具体行数

    MyISAM: 保存有表的总行数,如果select count() from table;会直接取出出该值。

    InnoDB: 没有保存表的总行数,如果使用select count(*) from table;就会遍历整个表,消耗相当大,但是在加了wehre条件后,myisam和innodb处理的方式都一样。

    10、CRUD操作

    MyISAM:如果执行大量的SELECT,MyISAM是更好的选择。

    InnoDB:如果你的数据执行大量的INSERT或UPDATE,出于性能方面的考虑,应该使用InnoDB表。

    11、 外键

    MyISAM:不支持

    InnoDB:支持

    三、sql优化简介

    1、什么情况下进行sql优化

    性能低、执行时间太长、等待时间太长、连接查询、索引失效。

    2、sql语句执行过程

    (1)编写过程

    select distinct ... from ... join ... on ... where ... group by ... having ... order by ... limit ...

    (2)解析过程

    from ... on ... join ... where ... group by ... having ... select distinct ... order by ... limit ...

    3、sql优化就是优化索引

    索引相当于书的目录。

    索引的数据结构是B+树。

    四、索引

    1、索引的优势

    (1)提高查询效率(降低IO使用率)

    (2)降低CPU使用率

    比如查询order by age desc,因为B+索引树本身就是排好序的,所以再查询如果触发索引,就不用再重新查询了。

    2、索引的弊端

    (1)索引本身很大,可以存放在内存或硬盘上,通常存储在硬盘上。

    (2)索引不是所有情况都使用,比如①少量数据②频繁变化的字段③很少使用的字段

    (3)索引会降低增删改的效率

    3、索引的分类

    (1)单值索引

    (2)唯一索引

    (3)联合索引

    (4)主键索引

    备注:唯一索引和主键索引唯一的区别:主键索引不能为null

    4、创建索引

    alter table user add INDEX `user_index_username_password` (`username`,`password`)

    5、MySQL索引原理 -> B+树

    MySQL索引的底层数据结构是B+树

    B+Tree是在B-Tree基础上的一种优化,使其更适合实现外存储索引结构,InnoDB存储引擎就是用B+Tree实现其索引结构。

    B-Tree结构图中每个节点中不仅包含数据的key值,还有data值。而每一个页的存储空间是有限的,如果data数据较大时将会导致每个节点(即一个页)能存储的key的数量很小,当存储的数据量很大时同样会导致B-Tree的深度较大,增大查询时的磁盘I/O次数,进而影响查询效率。在B+Tree中,所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上,而非叶子节点上只存储key值信息,这样可以大大加大每个节点存储的key值数量,降低B+Tree的高度。

    B+Tree相对于B-Tree有几点不同:

    非叶子节点只存储键值信息。
    所有叶子节点之间都有一个链指针。
    数据记录都存放在叶子节点中。
    将上一节中的B-Tree优化,由于B+Tree的非叶子节点只存储键值信息,假设每个磁盘块能存储4个键值及指针信息,则变成B+Tree后其结构如下图所示:

    通常在B+Tree上有两个头指针,一个指向根节点,另一个指向关键字最小的叶子节点,而且所有叶子节点(即数据节点)之间是一种链式环结构。因此可以对B+Tree进行两种查找运算:一种是对于主键的范围查找和分页查找,另一种是从根节点开始,进行随机查找。

    可能上面例子中只有22条数据记录,看不出B+Tree的优点,下面做一个推算:

    InnoDB存储引擎中页的大小为16KB,一般表的主键类型为INT(占用4个字节)或BIGINT(占用8个字节),指针类型也一般为4或8个字节,也就是说一个页(B+Tree中的一个节点)中大概存储16KB/(8B+8B)=1K个键值(因为是估值,为方便计算,这里的K取值为〖10〗^3)。也就是说一个深度为3的B+Tree索引可以维护10^3 * 10^3 * 10^3 = 10亿 条记录。

    实际情况中每个节点可能不能填充满,因此在数据库中,B+Tree的高度一般都在2~4层。MySQL的InnoDB存储引擎在设计时是将根节点常驻内存的,也就是说查找某一键值的行记录时最多只需要1~3次磁盘I/O操作。

    数据库中的B+Tree索引可以分为聚集索引(clustered index)和辅助索引(secondary index)。上面的B+Tree示例图在数据库中的实现即为聚集索引,聚集索引的B+Tree中的叶子节点存放的是整张表的行记录数据。辅助索引与聚集索引的区别在于辅助索引的叶子节点并不包含行记录的全部数据,而是存储相应行数据的聚集索引键,即主键。当通过辅助索引来查询数据时,InnoDB存储引擎会遍历辅助索引找到主键,然后再通过主键在聚集索引中找到完整的行记录数据。

    五、如何触发联合索引

    1、对user表建立联合索引username、password

    2、触发联合索引

    (1)使用联合索引的全部索引键可触发联合索引

    (2)使用联合索引的全部索引键,但是用or连接的,不可触发联合索引

    (3)单独使用联合索引的左边第一个字段时,可触发联合索引

    (4)单独使用联合索引的其它字段时,不可触发联合索引

    六、分析sql的执行计划---explain

    explain可以模拟sql优化执行sql语句。

    1、explan使用简介

    (1)用户表

    (2)部门表

    (3)未触发索引

    (4)触发索引

    (5)结果分析

    explain中第一行出现的表是驱动表。

    1. 指定了联接条件时,满足查询条件的记录行数少的表为[驱动表]
    2. 未指定联接条件时,行数少的表为[驱动表]

    对驱动表直接进行排序就会触发索引,对非驱动表进行排序不会触发索引。

    2、explain查询结果简介

    (1)id:SELECT识别符。这是SELECT的查询序列号。

    (2)select_type:SELECT类型:

    1. SIMPLE: 简单SELECT(不使用UNION或子查询)
    2. PRIMARY: 最外面的SELECT
    3. UNION:UNION中的第二个或后面的SELECT语句
    4. DEPENDENT UNION:UNION中的第二个或后面的SELECT语句,取决于外面的查询
    5. UNION RESULT:UNION的结果
    6. SUBQUERY:子查询中的第一个SELECT
    7. DEPENDENT SUBQUERY:子查询中的第一个SELECT,取决于外面的查询
    8. DERIVED:导出表的SELECT(FROM子句的子查询)

    (3)table:表名

    (4)type:联接类型

    1. system:表仅有一行(=系统表)。这是const联接类型的一个特例。
    2. const:表最多有一个匹配行,它将在查询开始时被读取。因为仅有一行,在这行的列值可被优化器剩余部分认为是常数。const用于用常数值比较PRIMARY KEY或UNIQUE索引的所有部分时。
    3. eq_ref:对于每个来自于前面的表的行组合,从该表中读取一行。这可能是最好的联接类型,除了const类型。它用在一个索引的所有部分被联接使用并且索引是UNIQUE或PRIMARY KEY。eq_ref可以用于使用= 操作符比较的带索引的列。比较值可以为常量或一个使用在该表前面所读取的表的列的表达式。
    4. ref:对于每个来自于前面的表的行组合,所有有匹配索引值的行将从这张表中读取。如果联接只使用键的最左边的前缀,或如果键不是UNIQUE或PRIMARY KEY(换句话说,如果联接不能基于关键字选择单个行的话),则使用ref。如果使用的键仅仅匹配少量行,该联接类型是不错的。ref可以用于使用=或<=>操作符的带索引的列。
    5. ref_or_null:该联接类型如同ref,但是添加了MySQL可以专门搜索包含NULL值的行。在解决子查询中经常使用该联接类型的优化。
    6. index_merge:该联接类型表示使用了索引合并优化方法。在这种情况下,key列包含了使用的索引的清单,key_len包含了使用的索引的最长的关键元素。
    7. unique_subquery:该类型替换了下面形式的IN子查询的ref:value IN (SELECT primary_key FROMsingle_table WHERE some_expr);unique_subquery是一个索引查找函数,可以完全替换子查询,效率更高。
    8. index_subquery:该联接类型类似于unique_subquery。可以替换IN子查询,但只适合下列形式的子查询中的非唯一索引:value IN (SELECT key_column FROM single_table WHERE some_expr)
    9. range:只检索给定范围的行,使用一个索引来选择行。key列显示使用了哪个索引。key_len包含所使用索引的最长关键元素。在该类型中ref列为NULL。当使用=、<>、>、>=、<、<=、IS NULL、<=>、BETWEEN或者IN操作符,用常量比较关键字列时,可以使用range
    10. index:该联接类型与ALL相同,除了只有索引树被扫描。这通常比ALL快,因为索引文件通常比数据文件小。
    11. all:对于每个来自于先前的表的行组合,进行完整的表扫描。如果表是第一个没标记const的表,这通常不好,并且通常在它情况下很差。通常可以增加更多的索引而不要使用ALL,使得行能基于前面的表中的常数值或列值被检索出。

    (5)possible_keys:possible_keys列指出MySQL能使用哪个索引在该表中找到行。注意,该列完全独立于EXPLAIN输出所示的表的次序。这意味着在possible_keys中的某些键实际上不能按生成的表次序使用。

    (6)key:key列显示MySQL实际决定使用的键(索引)。如果没有选择索引,键是NULL。要想强制MySQL使用或忽视possible_keys列中的索引,在查询中使用FORCE INDEX、USE INDEX或者IGNORE INDEX。

    (7)key_len:key_len列显示MySQL决定使用的键长度。如果键是NULL,则长度为NULL。注意通过key_len值我们可以确定MySQL将实际使用一个多部关键字的几个部分。

    (8)ref:ref列显示使用哪个列或常数与key一起从表中选择行。

    (9)rows:rows列显示MySQL认为它执行查询时必须检查的行数。

    (10)Extra:该列包含MySQL解决查询的详细信息。

    1. Distinct:MySQL发现第1个匹配行后,停止为当前的行组合搜索更多的行。
    2. Not exists:MySQL能够对查询进行LEFT JOIN优化,发现1个匹配LEFT JOIN标准的行后,不再为前面的的行组合在该表内检查更多的行。
    3. range checked for each record (index map: #):MySQL没有发现好的可以使用的索引,但发现如果来自前面的表的列值已知,可能部分索引可以使用。对前面的表的每个行组合,MySQL检查是否可以使用range或index_merge访问方法来索取行。
    4. Using filesort:MySQL需要额外的一次传递,以找出如何按排序顺序检索行。通过根据联接类型浏览所有行并为所有匹配WHERE子句的行保存排序关键字和行的指针来完成排序。然后关键字被排序,并按排序顺序检索行。
    5. Using index:从只使用索引树中的信息而不需要进一步搜索读取实际的行来检索表中的列信息。当查询只使用作为单一索引一部分的列时,可以使用该策略。
    6. Using temporary:为了解决查询,MySQL需要创建一个临时表来容纳结果。典型情况如查询包含可以按不同情况列出列的GROUP BY和ORDER BY子句时。
    7. Using where:WHERE子句用于限制哪一个行匹配下一个表或发送到客户。除非你专门从表中索取或检查所有行,如果Extra值不为Using where并且表联接类型为ALL或index,查询可能会有一些错误。
    8. Using sort_union(...), Using union(...), Using intersect(...):这些函数说明如何为index_merge联接类型合并索引扫描。
    9. Using index for group-by:类似于访问表的Using index方式,Using index for group-by表示MySQL发现了一个索引,可以用来查询GROUP BY或DISTINCT查询的所有列,而不要额外搜索硬盘访问实际的表。并且,按最有效的方式使用索引,以便对于每个组,只读取少量索引条目。

    通过相乘EXPLAIN输出的rows列的所有值,你能得到一个关于一个联接如何的提示。这应该粗略地告诉你MySQL必须检查多少行以执行查询。当你使用max_join_size变量限制查询时,也用这个乘积来确定执行哪个多表SELECT语句。

    🍅 Java学习路线:搬砖工逆袭Java架构师

    🍅 简介:Java领域优质创作者🏆、CSDN哪吒公众号作者✌ 、Java架构师奋斗者💪

    🍅 扫描主页左侧二维码,加入群聊,一起学习、一起进步 

    🍅 欢迎点赞 👍 收藏 ⭐留言 📝  

    展开全文
  • 堆组织就不说了,其索引中记录了记录所在位置的rowid,查找的时候先找索引,然后再根据索引rowid找到块中的行数据 索引组织,其行数据以索引形式存放,因此找到索引,就等于找到了行数据。 -- 堆组织的...
  • 在特殊情况下,它们可能是一多或多一的关系,即一张原始单证对应多个实体,或多张原始单证对应一个实体。  这里的实体可以理解为基本。明确这种对应关系后,我们设计录入界面大有好处。   〖例1〗...
  • 三级数据库复习笔记

    千次阅读 多人点赞 2018-04-03 12:45:24
    前言:这是我今年复习三级时自己做的笔记。为了加深记忆,基本上是纯手打。但是到最后几天的时候因为时间紧迫就主要是开始刷题而忘记了做笔记。所以内容不全,但是又懒得补了。。还有几漏了的。。但是现在是真的不...
  • 计算机三级(数据库)复习重点欢迎阅读我的计算机三级总结第章 数据库应用系统开发方法第二章 需求分析第三章 数据库结构设计(自底向上)第四章 数据库应用系统功能设计与实现第五章 UML与数据库应用系统第六章 ...
  • 三级模式两级映像/数据库系统结构

    万次阅读 多人点赞 2016-03-10 14:18:19
    如果从DBMS角度来看,数据库通常采用三级模式结构,也就是说DBMS内部的系统结构是三级模式结构2. 如果从数据库最终用户角度来看,数据库系统的结构可分为:单用户结构、主从式结构、分布式结构、客户/服务器、...
  • B+树比B树更适合做文件索引的原因

    万次阅读 多人点赞 2017-03-18 10:47:23
    B+树比B树更适合做文件索引的原因
  • 计算机三级(数据库)备考题目知识点总结

    千次阅读 多人点赞 2019-04-20 13:06:45
    计算机三级(数据库)备考题目知识点总结刷题所遇到的知识点总结考后总结 刷题所遇到的知识点总结 以下都是我在刷题时遇到的常考的知识点,供复习时做参考。 1.DBAS需求分析阶段的项重要工作是分析DBAS应具有的...
  • 索引建在与不同的空间

    千次阅读 2013-01-28 15:25:10
    Oracle 数据库的逻辑结构是由一些数据库对象... Oracle 数据库的物理结构从操作系统一查看,是由一个个的文件组成,从物理上可划分为:数据文件、日志文件、控制文件和参数文件。数据文件中存放了所有的数据信息;日志
  • 倒排索引

    千次阅读 2010-06-09 14:41:00
    这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值,而是由属性值来确定记录的位置,因而称为倒排索引(inverted index)。带有倒排索引的文件我们称为倒排索引文件,...
  • 索引

    千次阅读 2019-07-10 18:14:31
    索引种优化查询的数据数据结构 索引为什么快? 使用B+tree的数据结构,能够快速筛选出需要的记录,避免全扫描 为什么B+Tree快? 1 ,B+Tree拥有B-Tree的优点,深度浅,数据块大 2 ,因为只在叶子结点存储数据,...
  • ArcSDE 日志文件表

    千次阅读 2013-05-06 09:37:39
    今天跟大家介绍一下ArcSDE日志文件表,一直都想好好研究一下这块,因为基本上不太受大家重视,感兴趣的用户不是很多,但是一旦出现多用户并发查询或者版本操作的时候,这东西就显得非常重要了,而且根据不同的用户...
  • 何为主索引和二/辅助索引

    千次阅读 2013-09-22 15:16:43
    / DSO ,系统会自动生成一个索引基础上的重点领域,这是主索引。 此外,如果你想创造更多的索引,然后他们被称为二级索引。 主索引区别于二级索引都摆放了主索引包含中的重点领域和指针到了非键字段的。...
  • Oracle数据库的逻辑结构和物理结构  Oracle 数据库的逻辑结构是由一些数据库对象组成,如... Oracle 数据库的物理结构从操作系统一查看,是由一个个的文件组成,从物理上可划分为:数据文件、日志文件、控制文
  • 第1套 考试题库试题 数据库管理系统提供了数据定义语言(DDL),用于定义各种数据库对象。...目前某些系还没有招聘到教授,如果要用一个查询语句列出没有招聘到教授的系的系号和系名,用【外】连接操作可以
  • 三级数据库学习笔记

    千次阅读 2019-09-03 23:17:13
    备考三级数据库 由于是边刷真题边整理的,所以内容比较混乱
  • 利用Phoenix为HBase创建二级索引

    万次阅读 热门讨论 2015-05-17 15:10:35
    为什么需要Secondary Index对于HBase而言,如果想...如果不通过rowkey来查找数据,就必须逐行地比较每列的值,即全扫瞄。对于较大的,全扫瞄的代价是不可接受的。但是,很多情况下,需要从多角度查询数据。
  • MySQL 高级知识(索引、优化)

    万次阅读 多人点赞 2018-07-19 11:30:30
    连接池组件、管理服务和工具组件、SQL接口组件、查询分析器组件、优化器组件、缓冲组件、插件式存储引擎、物理文件; 1、连接层:主要完成一些类似于连接处理,授权认证及相关的方案; 2、服务层:主要完成大多数...
  • 计算机三级数据库知识点

    万次阅读 多人点赞 2018-09-15 21:35:40
    考完三级瞬间轻松,做题时记的知识点,(乱序版,懒得整理了,主要用于选择和填空)   dbo:database owner(数据库的创建者,创建该对象的用户.) guest:顾客(能够访问数据库中对象的数据,要求dbo分配权限给...
  • 2、method方法的表示-方法集合在class文件的什么位置 3、类中的method方法的实现代码---即机器码指令存放到哪了,并初步了解机器指令 4. 为什么没有在类中定义自己的构造函数,却可以使用new ClassName()构造...
  • 计算机三级-数据库技术

    万次阅读 多人点赞 2019-03-30 10:30:54
    三级数据库技术知识点总结 1 数据字典是系统种各类数据描述的集合,包括数据项,数据结构,数据流,数据存储和处理过程五部分 2 数据模型的三要素:数据结构、数据操作和完整性约束 3 数据库系统:一般由数据库...
  • 索引算法】倒排索引

    千次阅读 2016-08-10 18:26:15
    这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值,而是由属性值来确定记录的位置,因而称为倒排索引(inverted index)。带有倒排索引的文件我们称为倒排索引文件,...
  • 全国计算机等级考试 三级数据库精选填空100题

    千次阅读 多人点赞 2016-03-25 19:51:25
    在关系代数中对一个关系做操作以后新关系的元素个数(小于或等于)原来关系的元素。     51.  数据的存取按一次一个(元组)进行操作。     52. SQL 的集合处理方式与宿主语言的单记录处理方式...
  • 查看当前用户的缺省空间  SQL>select username,default_tablespace from user_users;  查看当前用户的角色 ... 查看当前用户的系统权限和表级权限  SQL>select * from user_sys_privs;  SQL>s
  • 全国计算机三级数据库技术

    千次阅读 多人点赞 2020-02-22 15:42:31
    全国计算机等级考试三级(数据库技术) :考试内容及要求 1.掌握数据库技术的基本概念、原理、方法和技术 2.能够使用SQL语言实现数据库操作 3.具备数据库系统安装、配置及数据库管理和维护的基本 4.掌握数据库管理...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 108,283
精华内容 43,313
关键字:

对一个具有三级索引表的文件