Jul18

Zip文件数据结构说明

Author: leeon  Click: 4418   Comments: 0 Category: 算法  Tag: zip

zip文件由三部分组成：压缩的文件内容源数据、压缩的目录源数据、目录结束标识结构

1、 压缩的文件内容源数据：

记录着压缩的所有文件的内容信息，其数据组织结构是对于每个文件都由file header 、file data、data descriptor三部分组成。

1）File header：用于标识该文件的开始，结构说明如下：

 

                               Header

Offset

Bytes

Description

译

0

4

Local file header signature = 0x04034b50 (read as a little-endian number)

文件头标识，值固定(0x04034b50)

4

2

Version needed to extract (minimum)

解压文件所需 pkware最低 版本 

6

2

General purpose bit flag

通用位标记

8

2

Compression method

压缩方法

10

2

File last modification time

文件最后修改时间

12

2

File last modification date

文件最后修改日期

14

4

CRC-32

说明采用的算法。

18

4

Compressed size

压缩后的大小。

22

4

Uncompressed size

非压缩的大小。

26

2

File name length (n)

文件名长度

28

2

Extra field length (m)

扩展区长度

30

n

File name

文件名

30+n

m

Extra field

扩展区

 

2）file data ：相应压缩文件的源数据。

 

3）data descriptor：用于标识该文件压缩结束，该结构只有在相应的header中通用标记字段的第３位设为１时才会出现，紧接在压缩文件源数据后。这个数据描述符只用在不能对输出的 ZIP 文件进行检索时使用。例如：在一个不能检索的驱动器（如：磁带机上）上的 ZIP 文件中。如果是磁盘上的ZIP文件一般没有这个数据描述符。

结构说明如下：

　　　Data descriptor

Offset

Bytes

Description[18]

译

 0

4

Local file header signature = 0x08074b50

本地header标记

 4

4

CRC-32

CRC-32

 8

4

Compressed size

压缩后大小

 12

4

Uncompressed size

非压缩的大小

 

2、 压缩的目录源数据

对于待压缩的目录而言，每一个子目录对应一个压缩目录源数据，记录该目录的描述信息。压缩包中所有目录源数据连续存储在整个归档包的最后，这样便于向包中追加新的文件。

结构说明如下：

Central directory file header

 

Offset

Bytes

Description[18]

译

 0

4

Central directory file header signature =0x02014b50

核心目录文件header标识=（0x02014b50）

 4

2

Version made by

压缩所用的pkware版本

 6

2

Version needed to extract (minimum)

解压所需pkware的最低版本

 8

2

General purpose bit flag

通用位标记

10

2

Compression method

压缩方法

12

2

File last modification time

文件最后修改时间

14

2

File last modification date

文件最后修改日期

16

4

CRC-32

CRC-32算法

20

4

Compressed size

压缩后大小

24

4

Uncompressed size

未压缩的大小

28

2

File name length (n)

文件名长度

30

2

Extra field length (m)

扩展域长度

32

2

File comment length (k)

文件注释长度

34

2

Disk number where file starts

文件开始位置的磁盘编号

36

2

Internal file attributes

内部文件属性

38

4

External file attributes

外部文件属性

42

4

Relative offset of local file header. This is the number of bytes between the start of the first disk on which the file occurs, and the start of the local file header. This allows software reading the central directory to locate the position of the file inside the ZIP file.

本地文件header的相对位移。

46

n

File name

目录文件名

46+n

m

Extra field

扩展域

46+n+m

k

File comment

文件注释内容

 

3、 目录结束标识结构

目录结束标识存在于整个归档包的结尾，用于标记压缩的目录数据的结束。

结构说明如下：

End of central directory record

Offset

Bytes

Description[18]

译

 0

4

End of central directory signature =0x06054b50

核心目录结束标记（0x06054b50）

 4

2

Number of this disk

当前磁盘编号

 6

2

Disk where central directory starts

核心目录开始位置的磁盘编号

 8

2

Number of central directory records on this disk

该磁盘上所记录的核心目录数量

10

2

Total number of central directory records

核心目录结构总数

12

4

Size of central directory (bytes)

核心目录的大小

16

4

Offset of start of central directory, relative to start of archive

核心目录开始位置相对于archive开始的位移

20

2

Comment length (n)

注释长度

22

n

Comment

注释内容
Sep2

【转载】btree索引和hash索引的区别

Author: sphinxsearch  Click: 5414   Comments: 0 Category: 算法  Tag: btree,hash

在mysql中，大多数索引（如 PRIMARY KEY,UNIQUE,INDEX和FULLTEXT）都是在BTREE中存储，但使用memory引擎可以选择BTREE索引或者HASH索引，两种不同类型的索引各自有其不同的使用范围。

=========以下节选网摘==========
Hash 索引结构的特殊性，其检索效率非常高，索引的检索可以一次定位，不像B-Tree 索引需要从根节点到枝节点，最后才能访问到页节点这样多次的IO访问，所以 Hash 索引的查询效率要远高于 B-Tree 索引。

 

可能很多人又有疑问了，既然 Hash 索引的效率要比 B-Tree 高很多，为什么大家不都用 Hash 索引而还要使用 B-Tree 索引呢？任何事物都是有两面性的，Hash 索引也一样，虽然 Hash 索引效率高，但是 Hash 索引本身由于其特殊性也带来了很多限制和弊端，主要有以下这些。

（1）Hash 索引仅仅能满足"=","IN"和"<=>"查询，不能使用范围查询。

由于 Hash 索引比较的是进行 Hash 运算之后的 Hash 值，所以它只能用于等值的过滤，不能用于基于范围的过滤，因为经过相应的 Hash 算法处理之后的 Hash 值的大小关系，并不能保证和Hash运算前完全一样。

（2）Hash 索引无法被用来避免数据的排序操作。

由于 Hash 索引中存放的是经过 Hash 计算之后的 Hash 值，而且Hash值的大小关系并不一定和 Hash 运算前的键值完全一样，所以数据库无法利用索引的数据来避免任何排序运算；

（3）Hash 索引不能利用部分索引键查询。

对于组合索引，Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值，而不是单独计算 Hash 值，所以通过组合索引的前面一个或几个索引键进行查询的时候，Hash 索引也无法被利用。

（4）Hash 索引在任何时候都不能避免表扫描。

前面已经知道，Hash 索引是将索引键通过 Hash 运算之后，将 Hash运算结果的 Hash 值和所对应的行指针信息存放于一个 Hash 表中，由于不同索引键存在相同 Hash 值，所以即使取满足某个 Hash 键值的数据的记录条数，也无法从 Hash 索引中直接完成查询，还是要通过访问表中的实际数据进行相应的比较，并得到相应的结果。

（5）Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高。

对于选择性比较低的索引键，如果创建 Hash 索引，那么将会存在大量记录指针信息存于同一个 Hash 值相关联。这样要定位某一条记录时就会非常麻烦，会浪费多次表数据的访问，而造成整体性能低下。

Jan6

什么是红黑树

Author: 百度百科  Click: 6757   Comments: 6 Category: 算法  Tag:
　　  
　　红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由Rudolf Bayer发明的，他称之为"对称二叉B树"，它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。
　　红黑树是一种很有意思的平衡检索树。它的统计性能要好于平衡二叉树(有些书籍根据作者姓名，Adelson-Velskii和Landis，将其称为AVL-树)，因此，红黑树在很多地方都有应用。在C++ STL中，很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化，这些修改提供了更好的性能，以及对set操作的支持)。
　红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:
　　性质1. 节点是红色或黑色。
　　性质2. 根是黑色。
　　性质3. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
　　性质4. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
　　An example of a red-black tree
　　这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。
　　要知道为什么这些特性确保了这个结果，注意到属性4导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据属性4所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。
　　在很多树数据结构的表示中，一个节点有可能只有一个子节点，而叶子节点包含数据。用这种范例表示红黑树是可能的，但是这会改变一些属性并使算法复杂。为此，本文中我们使用 "nil 叶子" 或"空(null)叶子"，如上图所示，它不包含数据而只充当树在此结束的指示。这些节点在绘图中经常被省略，导致了这些树好象同上述原则相矛盾，而实际上不是这样。与此有关的结论是所有节点都有两个子节点，尽管其中的一个或两个可能是空叶子。

分类

标签

武汉 互联网 javascript c++ apache linux rabbitmq java execvp it 平板 php miix jquery nginx shell mysql amqp 8寸 创业

归档

最新评论

默一在09:04:53评论了
Berkeley DB 由浅入深【转自架构师杨建】
Memory在14:09:22评论了
【原创】最佳PHP框架选择（phalcon,yaf,laravel,thinkphp,yii）
leo在17:57:04评论了
shell中使用while循环ssh的注意事项
呵呵哒啦在15:06:33评论了
【原创】最佳PHP框架选择（phalcon,yaf,laravel,thinkphp,yii）
jayden在23:39:32评论了
shell中使用while循环ssh的注意事项

我看过的书

链接

其他

访问本站种子 本站平均热度：6659 c° 本站链接数：27 个 本站标签数：447 个 本站被评论次数：92 次