Previous Next
View PDF 12 Logical Storage Structures Previous Next
View PDF 第12章逻辑存储结构
This chapter describes the nature of and relationships among logical storage structures. These structures are created and recognized by Oracle Database and are not known to the operating system. 本章介绍逻辑存储结构的特征及其之间的关系。这些结构由Oracle 数据库创建和识别，而对操作系统是透明的。
This chapter contains the following sections: 本章包含以下各节：
?Introduction to Logical Storage Structures
o Logical Storage Hierarchy
o Logical Space Management
?Overview of Data Blocks
o Data Blocks and Operating System Blocks
o Data Block Format
o Data Block Compression
o Space Management in Data Blocks
?Overview of Extents
o Allocation of Extents
o Deallocation of Extents
o Storage Parameters for Extents
?Overview of Segments
o User Segments
o Temporary Segments
o Undo Segments
o Segment Space and the High Water Mark ?Overview of Tablespaces
o Permanent Tablespaces
o Temporary Tablespaces
o Tablespace Modes
o Tablespace File Size ?逻辑存储结构简介
o逻辑存储层次结构
o逻辑空间管理
?数据块概述
o数据块和操作系统块
o数据块格式
o数据块压缩
o数据块的空间管理?扩展区概述
o分配扩展区
o释放扩展区
o扩展区的存储参数?段概述
o用户段
o临时段
o撤消段
o段空间和高水位标记?表空间概述
o永久表空间
o临时表空间
o表空间模式
o表空间文件大小
Introduction to Logical Storage Structures 逻辑存储结构简介
Oracle Database allocates logical space for all data in the database. The Oracle 数据库为数据库中的所有数据分配逻辑空间。数据库空间分配的逻
logical units of database space allocation are data blocks, extents, segments, and tablespaces. At a physical level, the data is stored in data files on disk (see Chapter 11, "Physical Storage Structures"). The data in the data files is stored in operating system blocks. 辑单元是数据块、扩展区、段、和表空间。而在物理级，数据被存储在磁盘上的数据文件中（请参阅第 11 章"物理存储结构"）。数据文件中的数据存储在操作系统块中。
Figure 12-1 is an entity-relationship diagram for physical and logical storage. The crow's foot notation represents a one-to-many relationship. 图 12-1 是一个物理和逻辑存储的实体关系图。乌鸦脚表示法表示一对多关系。
Figure 12-1 Logical and Physical Storage 图 12-1 逻辑和物理存储
Description of "Figure 12-1 Logical and Physical Storage"Description of "Figure 12-1 Logical and Physical Storage" Logical Storage Hierarchy 逻辑存储层次结构
Figure 12-2 shows the relationships among data blocks, extents, and segments within a tablespace. In this example, a segment has two extents stored in different data files. 图 12-2 显示了在表空间中的数据块、扩展区、和段之间的关系。在此示例中，一个段具有分别存储在不同数据文件中的两个扩展区。
Figure 12-2 Segments, Extents, and Data Blocks Within a
Tablespace
图 12-2 表空间中的段、扩展盘区、和数据块
Description of "Figure 12-2 Segments, Extents, and Data Blocks Within a Tablespace"Description of "Figure 12-2 Segments, Extents, and Data Blocks Within a Tablespace"
At the finest level of granularity, Oracle Database stores data in data blocks. One logical data block corresponds to a specific number of bytes of physical disk space, for example, 2 KB. Data blocks are the smallest units of storage that Oracle Database can use or allocate. 在最细的粒度级别， Oracle 数据库将数据存储为数据块。一个逻辑数据块对应于特定字节数的物理磁盘空间，比如 2 KB。数据块是Oracle 数据库可以使用或分配的最小存储单位。
An extent is a set of logically contiguous data blocks allocated for storing a specific type of information. In Figure 12-2, the 24 KB extent has 12 data blocks, while the 72 KB extent has 36 data blocks. 扩展区是一组逻辑上连续的数据块，被分配来用于存储特定类型的信息。在图12-2中，这个24 KB的扩展区有12 个数据块，而这个72 KB的扩展区有 36个数据块。
A segment is a set of extents allocated for a specific database object, such as a table. For example, the data for the employees table is stored in its own data segment, whereas each index for employees is stored in its own index segment. Every database object that consumes storage
consists of a single segment. 段是为一个特定数据库对象（如一个表）分配的一组扩展区。例如，employees表的数据存储在其自己的数据段中，而该表的每个索引存储在其自己的索引段中。会消耗存储空间的每个数据库对象都由单个段组成。
Each segment belongs to one and only one tablespace. Thus, all extents for a segment are stored in the same tablespace. Within a tablespace, a segment can include extents from multiple data files, as shown in Figure 12-2. For example, one extent for a segment may be stored in
users01.dbf, while another is stored in users02.dbf. A single extent can never span data files. 每个段属于且仅属于一个表空间。因此，一个段的所有扩展区存储在相同的表空间中。在一个表空间中，一个段可以包括多个数据文件中的扩展区，如图 12-2 所示。例如，段的一个扩展区可能存储在 users01.dbf中，而另一个存储在 users02.dbf 中。单个扩展区绝不会跨越多个数据文件。
See Also: 另见：
"Overview of Data Files"数据文件概述Logical Space Management 逻辑空间管理
Oracle Database must use logical space management to track and
allocate the extents in a tablespace. When a database object requires an extent, the database must have a method of finding and providing it.
Similarly, when an object no longer requires an extent, the database must
have a method of making the free extent available. Oracle 数据库必须使用逻辑空间管理来在表空间中跟踪并分配扩展区。当数据库对象需要扩展区时，该数据库必须有查找和分配扩展区的方法。同样，当对象不再需要扩展区时，数据库必须提供一种方法来重用可用空间。
Oracle Database manages space within a tablespace based on the type that you create. You can create either of the following types of tablespaces: Oracle 数据库基于您创建的表空间的类型来管理其中的空间。您可以创建下列类型的表空间之一：
?Locally managed tablespaces (default) ?本地管理表空间（默认值）
The database uses bitmaps in the tablespaces themselves to
manage extents. Thus, locally managed tablespaces have a part of the tablespace set aside for a bitmap. Within a tablespace, the
database can manage segments with automatic segment space
management (ASSM) or manual segment space management (MSSM). 数据库使用表空间本身中的位图来管理扩展区。因此，本地管理表空间需要预留表空间的一部分用于位图。在一个表空间中，数据库可以使用自动段空间管理（ASSM）或手动段空间管理（MSSM）来管理段。
?Dictionary-managed tablespaces ?字典管理表空间
The database uses the data dictionary to manage extents (see
"Overview of the Data Dictionary").
数据库使用数据字典来管理扩展区（请参阅"数据字典概述）。
Figure 12-3 shows the alternatives for logical space management in a tablespace. 图 12-3 显示了一个表空间中的逻辑空间管理方法的可选方案。
Figure 12-3 Logical Space Management 图 12-3 逻辑空间管理
Description of "Figure 12-3 Logical Space Management"Description of "Figure 12-3 Logical Space Management" Locally Managed Tablespaces 本地管理表空间
A locally managed tablespace maintains a bitmap in the data file header to track free and used space in the data file body. Each bit corresponds to a group of blocks. When space is allocated or freed, Oracle Database changes the bitmap values to reflect the new status of the blocks. 本地管理表空间在数据文件头中维护一个位图，以跟踪数据文件体中的可用空间和已用空间。每一位对应一组块。当空间被分配或释放时，Oracle 数据库更改位图值，以反映数据块的新状态。
The following graphic is a conceptual representation of bitmap-managed storage. A 1 in the header refers to used space, whereas a 0 refers to free space. 下面的图形是位图管理存储的概念表示。标头中的 1 是指已用空间，而 0 指可用空间。
Description of the illustration cncpt332.gif Description of the illustration cncpt332.gif
A locally managed tablespace has the following advantages: 本地管理表空间具有如下优势：
?Avoids using the data dictionary to manage extents ?避免使用数据字典来管理扩展区
Recursive operations can occur in dictionary-managed tablespaces if consuming or releasing space in an extent results in another operation that consumes or releases space in a data dictionary table or undo segment. 如果消耗或释放一个扩展区会导致在数据字典表或撤消段中消耗或释放空间，则在字典管理的表空间中会发生递归操作。
?Tracks adjacent free space automatically ?自动跟踪相邻的可用空间In this way, the database eliminates the need to coalesce free
extents.
通过这种方式，数据库消除了合并空闲扩展区的需要。?Determines the size of locally managed extents automatically ?自动确定本地管理扩展区的大小
Alternatively, all extents can have the same size in a locally managed tablespace and override object storage options. 或者，在本地管理表空间中所有的扩展区可以具有相同的大小，并覆盖对象存储选项。
Note: 注意：
Oracle strongly recommends the use of locally managed tablespaces with Automatic Segment Space Management. Oracle 强烈建议使用自动段空间管理的本地管理表空间。
Segment space management is an attribute inherited from the tablespace that contains the segment. Within a locally managed tablespace, the database can manage segments automatically or manually. For example, segments in tablespace users can be managed automatically while segments in tablespace tools are managed manually. 段空间管理是一个从包含该段的表空间继承来的属性。在一个本地管理表空间中，数据库可以自动地或手动地管理段。例如，users表空间中的段使用自动管理，而tools表空间中的段使用手动管理。
Automatic Segment Space Management 自动段空间管理(ASSM)
The ASSM method uses bitmaps to manage space. Bitmaps provide the
following advantages:
ASSM方法使用位图管理空间。位图提供了以下优点：?Simplified administration ?简化管理
ASSM avoids the need to manually determine correct settings for many storage parameters. Only one crucial SQL parameter controls space allocation: PCTFREE. This parameter specifies the percentage of space to be reserved in a block for future updates
(see "Percentage of Free Space in Data Blocks"). ASSM 可以避免手动确定许多存储参数的正确设置的需要。只有一个很关键的控制空间分配的 SQL 参数： PCTFREE。此参数指定要为块中保留用于将来的更新的空间百分比（请参阅"数据块中的可用空间百分比"）。
?Increased concurrency ?增强并发性
Multiple transactions can search separate lists of free data blocks, thereby reducing contention and waits. For many standard workloads, application performance with ASSM is better than the
performance of a well-tuned application that uses MSSM. 多个事务可以搜索多个相互独立的空闲数据块列表，从而减少争用和等待。对很多标准工作负载，使用ASSM的应用程序性能比使用优化得很好的使用MSSM的应用程序性能更好。
?Dynamic affinity of space to instances in an Oracle Real Application Clusters (Oracle RAC) environment ?对Oracle 真正应用集群（Oracle RAC）环境中实例的空间动态亲合性
ASSM is more efficient and is the default for permanent, locally managed
tablespaces.
ASSM 更有效，并且是永久性本地管理表空间的默认值。Note: 注意：
This chapter assumes the use of ASSM in all of its discussions of logical
storage space.
本章假定在逻辑存储空间的所有讨论中使用ASSM。
Manual Segment Space Management 手动段空间管理（MSSM）
The legacy MSSM method uses a linked list called a free list to manage
free space in the segment. For a database object that has free space, a free list keeps track of blocks under the high water mark (HWM), which is
the dividing line between segment space that is used and not yet used. As
blocks are used, the database puts blocks on or removes blocks from the free list as needed. 旧式的 MSSM 方法使用称为空闲列表的链表来管理段中的可用空间。对一个具有可用空间的数据库对象，有一个空闲列表会跟踪位于高水位线(HWM) 之下的数据块，所谓高水位，即已使用段空间和未使用段空间之间的分界线。当块被使用时，数据库根据需要将块放入空闲列表，或将块从空闲列表中删除。
In addition to PCTFREE, MSSM requires you to control space allocation with SQL parameters such as PCTUSED, FREELISTS, and FREELIST GROUPS. PCTUSED sets the percentage of free space that must exist in a currently used block for the database to put it on the free list. For example, if you set PCTUSED to 40 in a CREATE TABLE statement, then you cannot insert rows into a block in the segment until less than
40% of the block space is used. 除了 PCTFREE，MSSM 需要您使用额外的几个SQL 参数（如PCTUSED、FREELISTS、和FREELIST GROUPS）来控制空间分配。PCTUSED 设置在当前使用块中必须存在的可用空间百分比，当使用率低于该百分比时，数据库会将其放入空闲列表中。例如，如果CREATE TABLE 语句中设置PCTUSED为40，则只有当块空间使用少于 40%的情况下，您才能往段中的块插入新行。
As an illustration, suppose you insert a row into a table. The database checks a free list of the table for the first available block. If the row cannot fit in the block, and if the used space in the block is greater than or equal to PCTUSED, then the database takes the block off the list and searches for another block. If you delete rows from the block, then the database checks whether used space in the block is now less than PCTUSED. If so, then the database places the block at the beginning of the free list. 作为一个说明，假设向一个表中插入行。数据库检查该表的空闲列表，以查找第一个可用的块。如果行无法容纳进该块中，并在块中已使用空间大于或等于 PCTUSED，则数据库将该块从空闲列表中移除，并搜索另一个块。如果从块中删除行，则数据库检查块中的已使用空间现在是否小于PCTUSED。如果是，则数据库将该块置于空闲列表的开头。
An object may have multiple free lists. In this way, multiple sessions performing DML on a table can use different lists, which can reduce contention. Each database session uses only one free list for the duration of its session. 一个对象可能有多个空闲列表。通过这种方式，在表上执行 DML的多个会话可以使用不同列表，以减少争用。每个数据库会话在其会话持续时间只使用一个空闲列表。
As shown in Figure 12-4, you can also create an object with one or more free list groups, which are collections of free lists. Each group has a master free list that manages the individual process free lists in the
group. Space overhead for free lists, especially for free list groups, can be significant. 如图12-4 所示，你也可以创建具有一个或多个空闲列表组的对象，空闲列表组是空闲列表的集合。每个组有一个主空闲列表，用于管理组中的各个的处理空闲列表。空闲列表、尤其是空闲列表组的空间开销，可能非常显著。
Figure 12-4 Free List Groups 图 12-4 空闲列表组
Description of "Figure 12-4 Free List Groups"Description of "Figure 12-4 Free List Groups"
Managing segment space manually can be complex. You must adjust PCTFREE and PCTUSED to reduce row migration (see "Chained and Migrated Rows") and avoid wasting space. For example, if every used block in a segment is half full, and if PCTUSED is 40, then the database does not permit inserts into any of these blocks. Because of the difficulty
of fine-tuning space allocation parameters, Oracle strongly recommends ASSM. In ASSM, PCTFREE determines whether a new row can be inserted into a block, but it does not use free lists and ignores PCTUSED. 手动管理段空间可能会很复杂。您必须调整PCTFREE 和 PCTUSED，以减少行迁移（请参阅"链接行和迁移行"）和避免空间浪费。例如，如果段中的每个使用的块是半满，并且 PCTUSED 是 40，则数据库不允许向这些块插入新行。由于微调空间分配参数很困难， Oracle 强烈建议使用 ASSM。在ASSM中，由PCTFREE 确定是否可以将新行插入一个块中，但它不使用空闲列表，并忽略 PCTUSED。
See Also: 另见：
?Oracle Database Administrator's Guide to learn about locally
managed tablespaces
?《Oracle 数据库管理员指南》了解本地管理表空间
?Oracle Database 2 Day DBA and Oracle Database Administrator's Guide to learn more about automatic segment space management ?《Oracle 数据库 2 日DBA》和《Oracle 数据库管理员指南》了解自动段空间管理
?Oracle Database SQL Language Reference to learn about storage parameters such as PCTFREE and PCTUSED ?《Oracle 数据库 SQL 语言参考》了解存储参数，如 PCTFREE 和PCTUSED
Dictionary-Managed Tablespaces 字典管理表空间
A dictionary-managed tablespace uses the data dictionary to manage its extents. Oracle Database updates tables in the data dictionary whenever an extent is allocated or freed for reuse. For example, when a table needs an extent, the database queries the data dictionary tables, and searches 字典管理表空间使用数据字典来管理其扩展区。每当分配或释放了一个扩展区时， Oracle 数据库更新数据字典中的表。例如，当表需要扩展区时，数据库查询数据字典表，并搜索空闲扩展区。如果数据库找到了空间，则修改
for free extents. If the database finds space, then it modifies one data dictionary table and inserts a row into another. In this way, the database manages space by modifying and moving data. 一个数据字典表，并插入一行。按这种方式，数据库通过修改和移动数据来管理空间。
The SQL that the database executes in the background to obtain space for
database objects is recursive SQL. Frequent use of recursive SQL can have a negative impact on performance because updates to the data
dictionary must be serialized. Locally managed tablespaces, which are the
default, avoid this performance problem. 数据库在后台为数据库对象获取空间而执行的SQL是递归 SQL。频繁使用递归 SQL 可能会对性能有负面影响，因为必须串行化对数据字典的更新。而默认的本地管理表空间避免了这种性能问题。
See Also: 另见：
Oracle Database Administrator's Guide to learn how to migrate tablespaces from dictionary-managed to locally managed 《Oracle 数据库管理员指南》了解如何从字典管理表空间迁移到本地管理表空间
Overview of Data Blocks 数据块概述
Oracle Database manages the logical storage space in the data files of a database in units called data blocks, also called Oracle blocks or pages. A data block is the minimum unit of database I/O. Oracle 数据库以数据块（也称为Oracle 块或页）为单位，来管理数据库数据文件中的逻辑存储空间。数据块是数据库 I/O 的最小单位。
Data Blocks and Operating System Blocks 数据块和操作系统块
At the physical level, database data is stored in disk files made up of operating system blocks. An operating system block is the minimum unit of data that the operating system can read or write. In contrast, an Oracle block is a logical storage structure whose size and structure are not known to the operating system. 在物理级别，存储在磁盘文件中的数据库数据由操作系统块组成。操作系统块是操作系统可以读取或写入的最小数据单位。相比之下， Oracle 块是一个逻辑存储结构，其大小和结构对操作系统是透明的。
Figure 12-5 shows that operating system blocks may differ in size from data blocks. The database requests data in multiples of data blocks, not operating system blocks. 图 12-5显示操作系统块与数据块的大小可能有所不同。数据库按数据块（而不是按操作系统块）的倍数来请求数据。
Figure 12-5 Data Blocks and Operating System Blocks 图 12-5 数据块和操作系统块
Description of "Figure 12-5 Data Blocks and Operating System Blocks"Description of "Figure 12-5 Data Blocks and Operating System Blocks"
When the database requests a data block, the operating system translates this operation into a requests for data in permanent storage. The logical separation of data blocks from operating system blocks has the following implications: 当数据库请求一个数据块时，操作系统将此操作转换为对永久存储数据的多个请求。数据块与操作系统块的逻辑分离具有以下含义：
?Applications do not need to determine the physical addresses of
data on disk.
?应用程序不需要确定磁盘上的数据的物理地址。
?Database data can be striped or mirrored on multiple physical disks. ?数据库数据可以在多个物理磁盘上进行条带化或镜像。Database Block Size 数据库块大小
Every database has a database block size. The DB_BLOCK_SIZE initialization parameter sets the data block size for a database when it is created. The size is set for the SYSTEM and SYSAUX tablespaces and is the default for all other tablespaces. The database block size cannot be changed except by re-creating the database. 每个数据库都有一个数据库块大小。DB_BLOCK_SIZE 初始化参数在数据库被创建时设置其数据块大小。此大小是SYSTEM和SYSAUX表空间的大小，并且是其它表空间的默认大小。不能更改数据库的块大小，除非重新创建数据库。
If DB_BLOCK_SIZE is not set, then the default data block size is operating system-specific. The standard data block size for a database is 4 KB or 8 KB. If the size differs for data blocks and operating system blocks, then the data block size must be a multiple of the operating system block size. 如果尚未设置 DB_BLOCK_SIZE，则默认数据块大小特定于操作系统。数据库的标准数据块大小为 4 KB 或8 KB。如果数据块和操作系统块的大小不同，则数据块大小必须是操作系统块大小的整数倍。
See Also: 另见：
?Oracle Database Reference to learn about the DB_BLOCK_SIZE
initialization parameter
?《Oracle 数据库参考》了解 DB_BLOCK_SIZE初始化参数
?Oracle Database Administrator's Guide and Oracle Database Performance Tuning Guide to learn how to choose block sizes ?《Oracle 数据库管理员指南》和《Oracle 数据库性能调整指南》了解如何选择块大小
Tablespace Block Size 表空间块大小
You can create individual tablespaces whose block size differs from the DB_BLOCK_SIZE setting. A nonstandard block size can be useful when moving a transportable tablespace to a different platform. 你可以创建其块大小不同于DB_BLOCK_SIZE设定值的表空间。当你需要将一个可移动表空间移动到一个不同的平台时，非标准的块大小非常有用。
See Also: 另见：
Oracle Database Administrator's Guide to learn how to specify a
nonstandard block size for a tablespace
《Oracle 数据库管理员指南》了解如何为表空间指定非标准的块大小Data Block Format 数据块格式
Every data block has a format or internal structure that enables the database to track the data and free space in the block. This format is similar whether the data block contains table, index, or table cluster data. Figure 12-6 shows the format of an uncompressed data block (see "Data Block Compression" to learn about compressed blocks). 每个数据块有一个格式或内部结构，使得数据库能够跟踪块中的数据和可用空间。各种数据块的格式是类似的，无论其包含的是表、索引、或表簇数据。图 12-6 显示了一个未压缩的数据块的格式（请参阅"数据块压缩"，以了解压缩块）。
Figure 12-6 Data Block Format 图 12-6 数据块格式
Description of "Figure 12-6 Data Block Format"Description of "Figure 12-6 Data Block Format" Data Block Overhead 数据块开销
Oracle Database uses the block overhead to manage the block itself. The block overhead is not available to store user data. As shown in Figure 12-6, the block overhead includes the following parts: Oracle 数据库使用块开销来管理块本身。块开销不能用来存储用户数据。如图 12-6，块开销将包括以下部分：
?Block header ?块头
This part contains general information about the block, including disk address and segment type. For blocks that are transaction-managed, the block header contains active and historical
transaction information. 此部分包含关于块的一般信息，包括磁盘地址和段类型。对于事务管理块，其块头包含活动的和历史的事务信息。
A transaction entry is required for every transaction that updates the block. Oracle Database initially reserves space in the block header for transaction entries. In data blocks allocated to segments that support transactional changes, free space can also hold 每个更新块的事务都需要一个事务条目。Oracle 数据库预先在块头中为事务条目保留空间。在分配给段用于支持事务性更改的数据块中，当块头空间耗尽时，可用空间也可以容纳事务条目。事务条目所需的的空间取决于操作系统。但是，绝大多数操作系统中的事务条目
transaction entries when the header space is depleted. The space
required for transaction entries is operating system dependent.
However, transaction entries in most operating systems require
approximately 23 bytes.
需要大约 23 个字节。?Table directory ?表目录
For a heap-organized table, this directory contains metadata about tables whose rows are stored in this block. Multiple tables can store rows in the same block. 对于堆组织表，此目录包含有关其行存储在该块中的表的元数据。多个表可以将行存储在相同的块中。
?Row directory ?行目录
For a heap-organized table, this directory describes the location of
rows in the data portion of the block.
对于堆组织表，此目录描述该块的数据部分中的行的位置。
After space has been allocated in the row directory, the database
does not reclaim this space after row deletion. Thus, a block that is currently empty but formerly had up to 50 rows continues to have
100 bytes allocated for the row directory. The database reuses this space only when new rows are inserted in the block. 当已在行目录中分配空间后，即使在行被删除后，数据库也不会回收此空间。因此，就算某块现在是空的，但若之前曾经达到 50 行，则在行目录仍会保留已分配的100 字节。仅在块中插入新行时，数据库才会重用此空间。
Some parts of the block overhead are fixed in size, but the total size is variable. On average, the block overhead totals 84 to 107 bytes. 块开销的某些部分是大小固定的，但总的大小是可变的。平均起来，块开销总计在 84到107字节左右。
Row Format 行格式
The row data part of the block contains the actual data, such as table rows or index key entries. Just as every data block has an internal format, every row has a row format that enables the database to track the data in the row. 块的行数据部分包含实际数据，如表行或索引键条目等。正如每个数据块具有一个内部的格式，每一行也有一个行格式，使得数据库能够跟踪行中的数据。
Oracle Database stores rows as variable-length records. A row is contained in one or more row pieces. Each row piece has a row header and column data. Oracle 数据库以可变长度记录形式来存储行。行包含在一个或多个行片断中。每个行片断有一个行头和列数据。
Figure 12-7 shows the format of a row. 图 12-7 显示了行格式。Figure 12-7 The Format of a Row Piece 图 12-7 行片断格式
Description of "Figure 12-7 The Format of a Row Piece"Description of "Figure 12-7 The Format of a Row Piece"
Row Header 行头
Oracle Database uses the row header to manage the row piece stored in
the block. The row header contains information such as the following:
Oracle 数据库使用行头来管理存储在块中的行片断。行头包含以下信息：?Columns in the row piece ?行片断中的各列
?Pieces of the row located in other data blocks ?位于其他数据块中的各个行片断
If an entire row can be inserted into a single data block, then Oracle Database stores the row as one row piece. However, if all of the row data cannot be inserted into a single block or an update causes an existing row to outgrow its block, then the database stores the row in multiple row pieces (see "Chained and Migrated Rows"). A data block usually contains only one row piece per row. 如果整个行可以插入到一个数据块中，则Oracle数据库将该行存储为一个行片断。但是，如果所有行数据不能插入一个单一的块，或者一个更新导致现有的行不能容纳在原来的块中，则数据库将该行存储为多个行片断（请参阅"链接行和迁移行"）。数据块中通常每行只包含一个行片断。
?Cluster keys for table clusters (see "Overview of Table Clusters") ?表簇的簇键（见"表簇概述"）
A row fully contained in one block has at least 3 bytes of row header. 包含在一个块中的完全行至少有 3 个字节的行头。Column Data 列数据
After the row header, the column data section stores the actual data in the row. The row piece usually stores columns in the order listed in the CREATE TABLE statement, but this order is not guaranteed. For example, columns of type LONG are created last. 在行头之后的列数据部分存储行中的实际数据。行片断通常按CREATE TABLE语句中列出的顺序来存储列，但这个顺序并不总是能保证的。例如，LONG类型列总是在最后。
As shown in Figure 12-7, for each column in a row piece, Oracle Database
stores the column length and data separately. The space required
depends on the data type. If the data type of a column is variable length, then the space required to hold a value can grow and shrink with updates
to the data. 如图 12-7所示，对行片断中的每一列， Oracle 数据库独立地存储列长度和列数据。所需的空间取决于数据类型。如果列的数据类型是可变长度的，则用于容纳一个值所需的空间可能在其数据被更新时会增长和收缩。
Each row has a slot in the row directory of the data block header. The slot points to the beginning of the row. 每一行都在数据块标头的行目录中有一个槽位。槽位指向行的开始部分。
See Also: 另见：
"Table Storage" and "Index Storage""表存储"和"索引存储" Rowid Format Rowid格式
Oracle Database uses a rowid to uniquely identify a row. Internally, the rowid is a structure that holds information that the database needs to access a row. A rowid is not physically stored in the database, but is inferred from the file and block on which the data is stored. Oracle 数据库使用一个rowid唯一地标识一行。在内部，rowid 是一个结构，用于保存数据库访问行所需要的信息。一个 rowid 并不物理地存储在数据库中，而是从存储数据的文件和块推导而来的。
An extended rowid includes a data object number. This rowid type uses a base 64 encoding of the physical address for each row. The encoding characters are A-Z, a-z, 0-9, +, and /. 扩展的 rowid 包括数据对象号。这种rowid 类型使用每个行的物理地址的64进位编码。编码的字符为A-Z、a-z、0-9、+、和/。
Example 12-1 queries the ROWID pseudocolumn to show the extended rowid of the row in the employees table for employee 100. 示例12-1 查询ROWID 伪列来显示employees表中雇员 100 的所在行的扩展 rowid。
Example 12-1 ROWID Pseudocolumn 示例 12-1 ROWID 伪列
SQL> SELECT ROWID FROM employees WHERE employee_id = 100; ROWID
------------------
AAAPecAAFAAAABSAAA SQL> SELECT ROWID FROM employees WHERE employee_id = 100; ROWID
------------------
AAAPecAAFAAAABSAAA
Figure 12-8 illustrates the format of an extended rowid. 图 12-8 说明了一个扩展的 rowid 的格式。Figure 12-8 ROWID Format 图 12-8 ROWID 格式
Description of "Figure 12-8 ROWID Format"Description of "Figure 12-8 ROWID Format"
An extended rowid is displayed in a four-piece format, OOOOOOFFFBBBBBBRRR, with the format divided into the following components: 一个扩展 rowid 以一个四段式格式显示，OOOOOOFFFBBBBBBRRR，此格式分为以下几个组件：
?OOOOOO?OOOOOO
The data object number identifies the segment (data object AAAPec in Example 12-1). A data object number is assigned to every database segment. Schema objects in the same segment, such as a table cluster, have the same data object number. 数据对象号标识段（如示例中12-1中的数据对象AAAPec)。数据库中的每个段都被分配了一个数据对象号。同一段中的模式对象（如一个表簇）具有相同的数据对象号。
?FFF?FFF
The tablespace-relative data file number identifies the data file that contains the row (file AAF in Example 12-1). 表空间相对数据文件号，标识包含行的数据文件 (如示例12-1中的文件 AAF)。
?BBBBBB?BBBBBB
The data block number identifies the block that contains the row (block AAAABS in Example 12-1). Block numbers are relative to their data file, not their tablespace. Thus, two rows with identical block numbers could reside in different data files of the same tablespace. 数据块号标识包含行的块（如示例12-1中的块AAAABS）。块号是相对于他们的数据文件的，而不是其表空间。因此，具有相同块号的两行，可以驻留在同一表空间的不同数据文件中。
?RRR?RRR
The row number identifies the row in the block (row AAA in
Example 12-1).
行号标识块中的行（如示例 12-1中的 AAA）。
After a rowid is assigned to a row piece, the rowid can change in special circumstances. For example, if row movement is enabled, then the rowid can change because of partition key updates, Flashback Table operations, shrink table operations, and so on. If row movement is disabled, then a rowid can change if the row is exported and imported using Oracle Database utilities. 在一个 rowid被分配给一个行片断后，该rowid 在特殊情况下可以更改。例如，如果启用了行移动，则rowid 可能会因为分区键更新、闪回表操作、收缩表操作等而发生变化。如果禁用了行移动，则如果使用 Oracle 数据库实用程序导出和导入了行，其rowid可能会发生变化。
Note: 注意：
Internally, the database performs row movement as if the row were physically deleted and reinserted. However, row movement is considered an update, which has implications for triggers. 在内部，数据库执行行移动，就像行是被物理地删除、然后又重新插入。不过，行移动被认为是更新，会隐含触发触发器。
See Also: 另见：
?"Rowid Data Types"
?Oracle Database SQL Language Reference to learn about rowids ?"Rowid数据类型"
?《Oracle 数据库 SQL 语言参考》了解 rowid
Data Block Compression 数据块压缩
The database can use table compression to eliminate duplicate values in a data block (see "Table Compression"). This section describes the format of data blocks that use compression. 数据库可以使用表压缩来消除在数据块中的重复值（请参阅"表压缩"）。本节介绍使用压缩的数据块格式。
The format of a data block that uses basic and OLTP table compression is
essentially the same as an uncompressed block. The difference is that a
symbol table at the beginning of the block stores duplicate values for the rows and columns. The database replaces occurrences of these values
with a short reference to the symbol table. 使用基本表压缩和OLTP 表压缩的数据块，其格式与一个未压缩的块实质上是相同的。区别是使用位于块开头的符号表来存储行和列的重复值。数据库使用一个到符号表的短引用来替换这些重复出现的值。
Assume that the rows in Example 12-2 are stored in a data block for the seven-column sales table. 假定示例12-2中的行，存储在具有七个列的sales表的某个数据块中。
Example 12-2 Rows in sales Table 示例 12-2 sales表中的行
2190,13770,25-NOV-00,S,9999,23,161 2225,15720,28-NOV-00,S,9999,25,1450 34005,120760,29-NOV-00,P,9999,44,2376 9425,4750,29-NOV-00,I,9999,11,979 1675,46750,29-NOV-00,S,9999,19,1121 2190,13770,25-NOV-00,S,9999,23,161 2225,15720,28-NOV-00,S,9999,25,1450 34005,120760,29-NOV-00,P,9999,44,2376 9425,4750,29-NOV-00,I,9999,11,979 1675,46750,29-NOV-00,S,9999,19,1121
When basic or OLTP table compression is applied to this table, the database replaces duplicate values with a symbol reference. Example 12-3 is a conceptual representation of the compression in which the symbol * replaces 29-NOV-00 and % replaces 9999. 当在此表上应用基本或 OLTP 表压缩时，数据库会将重复值替换为一个符号引用。示例12-3是压缩的一个概念性展示，使用符号*替换了29-NOV-00，而使用%替换了9999。
Example 12-3 OLTP Compressed Rows in sales Table 示例12-3 sales表中的OLTP压缩行
2190,13770,25-NOV-00,S,%,23,161 2225,15720,28-NOV-00,S,%,25,1450 34005,120760,*,P,%,44,2376 9425,4750,*,I,%,11,979
1675,46750,*,S,%,19,1121 2190,13770,25-NOV-00,S,%,23,161 2225,15720,28-NOV-00,S,%,25,1450 34005,120760,*,P,%,44,2376 9425,4750,*,I,%,11,979
1675,46750,*,S,%,19,1121
Table 12-1 conceptually represents the symbol table that maps symbols to values. 表 12-1从概念上展示了从符号映射到值的符号表。
Table 12-1 Symbol Table 表 12-1 符号表
Symbol Value Column Rows * 29-NOV-00 3 958-960 % 9999 5 956-960 称号值列行
* 29-NOV-00 3 958-960 % 9999 5 956-960
Space Management in Data Blocks 数据块的空间管理
As the database fills a data block from the bottom up, the amount of free
space between the row data and the block header decreases. This free space can also shrink during updates, as when changing a trailing null to a
nonnull value. The database manages free space in the data block to optimize performance and avoid wasted space. 随着数据库从底向上不断填充数据块，在行数据和块头之间的可用空间就会逐渐减少。在更新期间，当将一个尾部空值更改为非空值时，可用空间也会变少。数据库会管理数据块中的可用空间，以优化性能并避免空间浪费。
Note: 注意：
This section assumes the use of automatic segment space management. 本节假定使用自动段空间管理。Percentage of Free Space in Data Blocks 数据块中的可用空间百分比
The PCTFREE storage parameter is essential to how the database manages free space. This SQL parameter sets the minimum percentage of a data reserved as free space for updates to existing rows. Thus, PCTFREE is important for preventing row migration and avoiding wasted space. PCTFREE 存储参数对于数据库如何管理其可用空间非常重要。此SQL 参数设置为更新现有的行而保留的可用空间最小百分比。因此，PCTFREE 对于防止行迁移并避免空间浪费非常重要。
For example, assume that you create a table that will require only occasional updates, most of which will not increase the size of the existing data. You specify the PCTFREE parameter within a CREATE TABLE statement as follows: 例如，假设您创建了一个只是偶尔需要更新的表，其中大多数更新都不会增加现有数据的大小。你可以在CREATE TABLE 语句中指定 PCTFREE 参数，如下所示：
CREATE TABLE test_table (n NUMBER) PCTFREE 20; CREATE TABLE test_table (n NUMBER) PCTFREE 20;
Figure 12-9 shows how a PCTFREE setting of 20 affects space management. The database adds rows to the block over time, causing the row data to grow upwards toward the block header, which is itself 图 12-9 显示了将 PCTFREE 设置为 20是如何影响空间管理的。数据库不断将行添加到块，这将导致行数据朝着块头方向向上不断增长，而块头本身又朝行数据方向向下不断扩大。该PCTFREE 设置确保至少 20%的数据块是空
expanding downward toward the row data. The PCTFREE setting ensures that at least 20% of the data block is free. For example, the database prevents an INSERT statement from filling the block so that the row data and header occupy a combined 90% of the total block space, leaving only 10% free. 闲的。例如，数据库可以防止一个INSERT语句填充该块，使行数据和标头一共占据块总空间的90%，而只剩 10%可用空间。
Figure 12-9 PCTFREE 图 12-9 PCTFREE
Description of "Figure 12-9 PCTFREE"Description of "Figure 12-9 PCTFREE" Note: 注意：
This discussion does not apply to LOB data types, which do not use the PCTFREE storage parameter or free lists. See "Overview of LOBs". 本讨论并不适用于LOB 数据类型，它不使用PCTFREE存储参数或空闲列表。请参阅 "LOB概述"。
See Also: 另见：
Oracle Database SQL Language Reference for the syntax and semantics of the PCTFREE parameter 《Oracle 数据库 SQL 语言参考》关于PCTFREE 参数的语法和语义
Optimization of Free Space in Data Blocks 优化数据块中的可用空间
While the percentage of free space cannot be less than PCTFREE, the amount of free space can be greater. For example, a PCTFREE setting of 20% prevents the total amount of free space from dropping to 5% of the block, but permits 50% of the block to be free space. The following SQL statements can increase free space: 虽然可用空间的百分比不能小于PCTFREE，但其可用空间量可以更大。例如， 20%的 PCTFREE 设置可以防止可用空间总量少于5%，但它允许该块具有50%的可用空间。下面的 SQL 语句可能会增加可用空间：
?DELETE statements
?UPDATE statements that either update existing values to smaller values or increase existing values and force a row to migrate
?INSERT statements on a table that uses OLTP compression If inserts fill a block with data, then the database invokes block
compression, which may result in the block having more free space. ?DELETE语句
?UPDATE语句，要么将现有值更新为更小的值，或者增大现有值并被强制迁移到另一个行
?在使用了OLTP压缩的表上的INSERT语句
如果插入操作往块中填充了数据，则数据库会调用块压缩，结果可能会导致在块中有更多的可用空间。
The space released is available for INSERT statements under the
following conditions:
在下列条件下，释放的空间可供 INSERT 语句使用：
?If the INSERT statement is in the same transaction and after the statement that frees space, then the statement can use the space. ?If the INSERT statement is in a separate transaction from the statement that frees space (perhaps run by another user), then the statement can use the space made available only after the other transaction commits and only if the space is needed. ?如果 INSERT 语句是位于释放空间的语句之后，且处于相同的事务中，则该语句可以使用已释放的空间。
?如果INSERT 语句与释放空间的语句位于各自单独的事务中（也许是由另一个用户运行的），只要另一个事务已提交，则该语句可以在需要此空间时使用它。
See Also: 另见：
Oracle Database Administrator's Guide to learn about OLTP compression 《Oracle 数据库管理员指南》了解 OLTP 压缩Coalescing Fragmented Space 合并碎片空间
Released space may or may not be contiguous with the main area of free space in a data block, as shown in Figure 12-10. Noncontiguous free space is called fragmented space. 被释放的空间与数据块可用空间的主要区域可能是连续的，也可能是不连续的，如图 12-10 所示。不连续的可用空间称为碎片空间。
Figure 12-10 Data Block with Fragmented Space 图 12-10 具有碎片空间的数据块
Description of "Figure 12-10 Data Block with Fragmented Space"Description of "Figure 12-10 Data Block with Fragmented Space"
Oracle Database automatically and transparently coalesces the free space of a data block only when the following conditions are true: 只有在满足以下条件时，Oracle 数据库才会自动且透明地合并数据块中的可用空间，
?An INSERT or UPDATE statement attempts to use a block that contains sufficient free space to contain a new row piece. ?INSERT或UPDATE语句试图使用的块，包含足够的可用空间来容纳新的行片断。
?The free space is fragmented so that the row piece cannot be inserted in a contiguous section of the block. ?可用空间已被碎片化，以至于该行片断不能插入到块中的某一个连续区域。
After coalescing, the amount of free space is identical to the amount before the operation, but the space is now contiguous. Figure 12-11 shows a data block after space has been coalesced. 合并后，可用空间量与操作之前是相同的，只不过该空间现在已成为连续的。图 12-11 显示一个数据块的空间被合并了之后的情况。
Figure 12-11 Data Block After Coalescing Free Space 图 12-11 数据块合并后的可用空间
第1章绪论 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 答案： 数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。 数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。 数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。 逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 存储结构：数据对象在计算机中的存储表示，也称为物理结构。 抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。 2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 答案： 例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。 这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。 即相同的逻辑结构，可以对应不同的存储结构。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 答案： （1）集合结构 数据元素之间除了“属于同一集合”的关系外，别无其他关系。例如，确定一名学生是否为班级成员，只需将班级看做一个集合结构。 （2）线性结构 数据元素之间存在一对一的关系。例如，将学生信息数据按照其入学报到的时间先后顺序进行排列，将组成一个线性结构。 （3）树结构
四种基本的存储结构 Prepared on 22 November 2020
数据的四种基本存储方法 数据的存储结构可用以下四种基本存储方法得到： （1）顺序存储方法 该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。 由此得到的存储表示称为顺序存储结构（Sequential Storage Structure），通常借助程序语言的数组描述。 该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。 （2）链接存储方法 该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构（Linked Storage Structure）,通常借助于程序语言的指针类型描述。 （3）索引存储方法 该方法通常在储存结点信息的同时，还建立附加的索引表。
索引表由若干索引项组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（Dense Index）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引(Spare Index)。索引项的一般形式是： (关键字、地址) 关键字是能唯一标识一个结点的那些数据项。稠密索引中索引项的地址指示结点所在的存储位置；稀疏索引中索引项的地址指示一组结点的起始存储位置。 （4）散列存储方法 该方法的基本思想是：根据结点的关键字直接计算出该结点的存储地址。 四种基本存储方法，既可单独使用，也可组合起来对数据结构进行存储映像。 同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，视具体要求而定，主要考虑运算方便及算法的时空要求。 数据结构三方面的关系
数据结构中常用的逻辑结构和存储结构 一、概念 数据是指由有限的符号（比如，"0"和"1"，具有其自己的结构、操作、和相应的语义）组成的元素的集合。结构是元素之间的关系的集合。 数据结构是在整个计算机科学与技术领域上广泛被使用的术语。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。 数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系即逻辑结构，而物理上的数据结构反映成分数据在计算机内部的存储安排即存储结构。数据结构是数据存在的形式。 数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。因而研究数据结构的逻辑结构与存储结构显得十分重要。 二、结构分析 （一）逻辑结构 数据的逻辑结构是对数据之间关系的描述，有时就把逻辑结构简称为数据结构。逻辑结构形式地定义为（K，R）（或（D，S）），其中，K是数据元素的有限集，R是K上的关系的有限集。 逻辑结构元素决定输入、存储、发送、处理和信息传递的基本操作功能，常将逻辑结构元素称为逻辑模块。逻辑结构元素可以是计算机操作系统、终端模块、通信程序模块等。逻辑结构元素还可以是相关的几个逻辑模块联合起来的更复杂的实体。分析逻辑结构元素的相互作用，应考虑整个系统的操作，研究处理与信息流有关的进程（操作系统中的一个概念，表示程序的一次执行），并决定系统的逻辑资源。 逻辑结构有四种基本类型：集合结构、线性结构、树状结构和网络结构。表和树是最常用的两种高效数据结构，许多高效的算法能够用这两种数据结构来设计实现。 一、基本分类 数据的逻辑结构指数据元素之间的逻辑关系，分两种，线性结构和非线性结构。 线性结构：有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前驱和一个直接后继。）线性表就是一个典型的线性结构它有四个基本特征：1．集合中必存在唯一的一个"第一个元素"； 2．集合中必存在唯一的一个"最后的元素"； 3．除最后元素之外，其它数据元素均有唯一的"后继"； 4．除第一元素之外，其它数据元素均有唯一的"前驱"。 相对应于线性结构，非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个直接后继。常见的非线性结构有：树(二叉树等)，图(网等)。 二、常用结构
数据的四种基本存储方法 数据的存储结构可用以下四种基本存储方法得到： （1）顺序存储方法 ???该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。 ???由此得到的存储表示称为顺序存储结构（SequentialStorageStructure），通常借助程序语言的数组描述。 该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。 （2）链接存储方法 ???该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构（LinkedStorageStructure）,通常借助于程序语言的指针类型描述。 （3）索引存储方法 ???该方法通常在储存结点信息的同时，还建立附加的索引表。 ???索引表由若干索引项组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（DenseIndex）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引(SpareIndex)。索引项的一般形式是：
????????????????????(关键字、地址) 关键字是能唯一标识一个结点的那些数据项。稠密索引中索引项的地址指示结点所在的存储位置；稀疏索引中索引项的地址指示一组结点的起始存储位置。（4）散列存储方法 ???该方法的基本思想是：根据结点的关键字直接计算出该结点的存储地址。 四种基本存储方法，既可单独使用，也可组合起来对数据结构进行存储映像。 同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，视具体要求而定，主要考虑运算方便及算法的时空要求。 数据结构三方面的关系 数据的逻辑结构、数据的存储结构及数据的运算这三方面是一个整体。孤立地去理解一个方面，而不注意它们之间的联系是不可取的。 存储结构是数据结构不可缺少的一个方面：同一逻辑结构的不同存储结构可冠以不同的数据结构名称来标识。 【例】线性表是一种逻辑结构，若采用顺序方法的存储表示，可称其为顺序表；若采用链式存储方法，则可称其为链表；若采用散列存储方法，则可称为散列表。
数据结构复习笔记 作者: 网络转载发布日期: 无 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，有时一个数据元素可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。如整数这个集合中，10这个数就可称是一个数据元素.又比如在一个数据库(关系式数据库)中，一个记录可称为一个数据元素，而这个元素中的某一字段就是一个数据项。 数据结构的定义虽然没有标准，但是它包括以下三方面内容：逻辑结构、存储结构、和对数据的操作。这一段比较重要，我用自己的语言来说明一下，大家看看是不是这样。 比如一个表(数据库)，我们就称它为一个数据结构，它由很多记录(数据元素)组成，每个元素又包括很多字段(数据项)组成。那么这张表的逻辑结构是怎么样的呢? 我们分析数据结构都是从结点(其实也就是元素、记录、顶点，虽然在各种情况下所用名字不同，但说的是同一个东东)之间的关系来分析的，对于这个表中的任一个记录(结点)，它只有一个直接前趋，只有一个直接后继(前趋后继就是前相邻后相邻的意思)，整个表只有一个开始结点和一个终端结点，那我们知道了这些关系就能明白这个表的逻辑结构了。 而存储结构则是指用计算机语言如何表示结点之间的这种关系。如上面的表，在计算机语言中描述为连续存放在一片内存单元中，还是随机的存放在内存中再用指针把它们链接在一起，这两种表示法就成为两种不同的存储结构。(注意，在本课程里，我们只在高级语言的层次上讨论存储结构。) 第三个概念就是对数据的运算，比如一张表格，我们需要进行查找，增加，修改，删除记录等工作，而怎么样才能进行这样的操作呢? 这也就是数据的运算，它不仅仅是加减乘除这些算术运算了，在数据结构中，这些运算常常涉及算法问题。 弄清了以上三个问题，就可以弄清数据结构这个概念。 -------------------------------------------------------------------------------- 通常我们就将数据的逻辑结构简称为数据结构，数据的逻辑结构分两大类：线性结构和非线性结构(这两个很容易理解) 数据的存储方法有四种：顺序存储方法、链接存储方法、索引存储方法和散列存储方法。-------------------------------------------------------------------------------- 下一个是难点问题，就是算法的描述和分析，主要是算法复杂度的分析方法及其运用。首先了解一下几个概念。一个是时间复杂度，一个是渐近时间复杂度。前者是某个算法的时间耗费，它是该算法所求解问题规模n的函数，而后者是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度，因此，在算法分析时，往往对两者不予区分，经常是将渐近时间复杂度T(n)=O(f(n)简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。 此外，算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。 常见的时间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。 时间复杂度的分析计算请看书本上的例子，然后我们通过做练习加以领会和巩固。 数据结构习题一 --------------------------------------------------------------------------------
2007 C C C 语言的特点，简单的C 程序介绍，C 程序的上机步骤。1 、算法的概念2、简单的算法举例3、算法的特性4、算法的表示（自然语言、流程图、N-S 图表示） 1 、 C 的数据类型、常量与变星、整型数据、实型数据、字符型数据、字符串常量。2、 C 的运算符运算意义、优先级、结合方向。3、算术运算符和算术表达式，各类数值型数据间的混合运算。4、赋值运算符和赋值表达式。5、逗号运算符和逗号表达式。 1 、程序的三种基本结构。2、数据输入输出的概念及在C 语言中的实现。字符数据的输入输出，格式输入与输出。 1 、关系运算符及其优先级，关系运算和关系表达式。2、逻辑运算符及其优先级，逻辑运算符和逻辑表达式。3、if语句。if语句的三种形式，if语句的嵌套，条件运算符。4、switch 语句. 1 、while 语句。2、do/while 语句。3、for 语句。4、循环的嵌套。5、break 语句和continue 语句。1 、一维数组的定义和引用。2、二维数组的定义和引用。3、字符数组。4、字符串与字符数组。5、字符数组的输入输出。6、字符串处理函数1 、函数的定义。2、函数参数和函数的值，形式参数和实际参数。3、函数的返回值。4、函数调用的方式，函数的声明和函数原型。5、函数的嵌套调用。 6、函数的递归调用。 7、数组作为函数参数。 8、局部变量、全局变量的作用域。 9、变量的存储类别，自动变星，静态变量。1 、带参数的宏定义。2、“文件包含”处理。1 、地址和指针的概念。2、变量的指针和指向变量的指针变量。3、指针变量的定义
和引用。4、指针变量作为函数参数。5、数组的指针和指向数组的指针变量。6、指向数组元素的指针。7、通过指针引用数组元素。8、数组名作函数参数。9、二维数组与指针。 1 0、指向字符串的指针变星。字符串的指针表示形式，字符串指针作为函数参数。11 、字符指针变量和字符数组的异同。1 2、返回指针值的函数。1 3、指针数组。1 、定义结构体类型变星的方法。2、结构体变量的引用。3、结构体变量的初始化。4、结构体数组5、指向结构体类型数据的指针。6、共用体的概念，共用体变量的定义和引用，共用体类型数据的特点。typedef 1 、数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。2、数据结构的两大类逻辑结构和常用的存储表示方法。3、算法描述和算法分析的方法，对于一般算法能分析出时间复杂度。 1 、线性表的逻辑结构特征。2、线性表上定义的基本运算。3、顺序表的特点，即顺序表如何反映线性表中元素之间的逻辑关系。4、顺序表上的插入、删除操作及其平均时间性能分析。5、链表如何表示线性表中元素之间的逻辑关系。6、链表中头指针和头结点的使用。7、单链表上实现的建表、查找、插入和删除等基本算法，并分析其时间复杂度。8、顺序表和链表的主要优缺点。9、针对线性表上所需的主要操作，选择时空性能优越的存储结构。 1 、栈的逻辑结构特点．栈与线性表的异同。2、顺序栈和链栈实现的进栈、退栈等基本算法。3、栈的空和栈满的概念及其判定条件。4、队列的逻辑结构特点，队列与线性表的异同。5、顺序队列(主要是循
江苏省计算机等级考试一级历年真题(06-12) 第六章信息系统与数据 第六章信息系统与数据库 本章知识点与学习要求 I．了解信息系统的结构、分类和发展趋势。 2．了解业务信息处理系统、信息检索系统和信息分析系统的区别和特点。 3．区分数据库、数据库管理系统、数据库系统的不同概念和内容． 4．描述数据模型、掌握数据库系统和应用的相关知识。 5．了解并初步掌握信息系统的开发的过程、方法和技术。 6．了解信息系统运行和维护的内容和方法。 7．了解典型信息系统的应用。 8．解释什么是信息化。信息化建设包括哪些主要内容。 一、判断题 1. 信息系统有各种类型，某企业内部用于进行日常业务处理的系统称为信息检索系统。 2．DBMS是DBS的核心软件。 3．DBS是帮助用户建立、使用和管理数据库的一种计算机软件。
4. SQL有两种使用方式，既可以将SQL语句作为命令以交互方式使用．也可以将它嵌入到某高级语言源程序中。 5．SOL语言是为关系数据库配备的过程化语言。 6．SQL语言是一种面向数据库系统的结构化查询语言。 7．从数据管理技术来看，数据库系统与文件系统的重要区别之一是数据无冗余。 8. 对数据库设计的评价、调整等维护工作应由数据库管理员(DBA)来完成。 9．关系模式的主键是该模式的某个属性组，它能惟一确定二维表中的一个元组。 10. 关系模式用R(AI，A2，?，Am)表示，仅仅说明该关系的语法，并不是合乎该语法的每个元组都能成为关系R中的一个元组。 11. 关系模型的逻辑数据结构是二维表关系模式是二维表的结构的描述。关系是二维表的内容。 12．关系模型中的模式对应于文件系统中的记录。 13．关系数据库系统中的关系模式是静态的，而关系是动态的。 14. 关系数据模型的存取路径对用户透明，可以简化程序员的编程工作，数据独立性好。 15. 关系数据模型的存取路径对用户透明，其意是指用户编程时不用考虑数据的存取路径。
Oracle 逻辑存储结构 逻辑存储结构是Oracle 数据库存储结构的核心内容，对Oracle 数据库的所有操作都会涉及到其逻辑存储结构。数据库的逻辑结构是从逻辑的角度分析数据库的构成，即创建数据库后形成的逻辑概念之间的关系。在逻辑上，Oracle 将保存的数据划分为一个个小单元来进行存储和维护，高一级的存储单元由一个或多个低一级的存储单元组成。Oracle 的逻辑存储单元从小到大依次为：数据块（DA TA BLOCKS ）、盘区（EXTENT ）、段（SEGMENTS ）和表空间（TABLE SPACES ），图2-2显示了各逻辑单位之间的关系。 数据库 ...表空间 表空间段 段盘区 数据块盘区数据块 段段数据库...表空间表空间段段盘区数据块盘区数据块段 段 图2-2 数据库的逻辑存储组成 由图2-2可知，Oracle 数据库由多个表空间组成，而表空间又由许多段组成，段由多个盘区组成，盘区又由多个数据块组成。 1 数据块 数据块是Oracle 用来管理存储空间的最小单元，也是执行数据库输入输出操作时的最小单位。相对应地，操作系统执行输入输出操作的最小单位为一个操作系统块的大小。在操作系统中，执行I/O 操作是以操作系统块为单位，而在Oracle 中，执行的I/O 操作以Oracle 数据块为单位。 Oracle 块的大小是操作系统块大小的整数倍。以Windows NT 操作系统为例，NTFS 格式的磁盘分区一般为4KB 大小，因此Oracle 块的大小为8KB 等。数据块的标准大小由初始化参数DB_BLOCK_SIZE 确定，具有标准大小的块被称为标准块。Oracle 支持在同一个数据库中使用多种大小的块，与标准块大小不同的块称为非标准块。 可以通过查询V$PARAMETER 数据字典，可以获得参数DB_BLACK_SIZE 的值，该参数值同时也是数据块的尺寸大小。例如： SQL> select name,value 2 from v$parameter where name ='db_block_size'; NAME V ALUE --------------------------- -------------------------- db_block_size 8192 在数据块中可以存储各种类型的数据，如表数据、索引数据、簇数据等。无论数据块中存放何种类型的数据，块都具有相同的结构，图2-3列出一个Oracle 块的基本结构。
EMC DMX存储的物理架构与逻辑架构 一.DMX存储概述 DMX存储硬件的物理与逻辑架构能够实现最大限度的将一个lun 的io 最大限度分摊给硬盘,DAE盘阵的环路; 一个lun 的io 同时也平均分摊给后端的存储cpu . 从后面文档设备连接的介绍可以知晓. DMX的架构做到了最大限度的打散数据以达到性能最大化;性能最大化的硬件配置是一个控制柜加两个与控制柜存储cpu端口直连的磁盘柜; 存储卷vol 以及4个vol meta(绑定) 条带化以后就避免了热点(hot block) 读写的问题. 将任何一个lun的读写io 操作做到由最多的硬件资源来支撑. 硬件资源主要是硬盘,DAE盘阵环路,存储cpu,存储缓存. DMX存储安装配置是通过加载预先配置好的bin file 来部署的; bin file 定义了物理架构与逻辑架构的配置定义整个存储当前硬件配置如何被使用规划好,以后修改配置就得重新装载bin file 也就是重新配置整个存储. Bin file的加载以及整个存储的管理通过console服务器上的软件symmwin来操作,console服务器通过电话线moden 与EMC 支持中心连通. EMC技术人员通过电话线的拨号拨入方式可以做到完全掌控存储设备. 本文档关注存储设备架构方面,管理方面的gk盘,ecc等不做赘述. 二.E MC DMX 存储的物理架构 1.存储外观及各个模块介绍 (1)外观 DMX由一个控制柜加磁盘柜组成, 通常带2个或者5个磁盘柜 我们公司为了性能最大化,配置满配的前端后端卡,只挂2个磁盘柜.再扩展磁盘 机柜只增加空间,性能不增长.
, BAY BAY (2)物理构成模块图示: (打开机柜门前视图)
第1章绪论 习题 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 4．存储结构由哪两种基本的存储方法实现？ 5．选择题 （1）在数据结构中，从逻辑上可以把数据结构分成（）。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．部结构和外部结构 （2）与数据元素本身的形式、容、相对位置、个数无关的是数据的（）。 A．存储结构 B．存储实现 C．逻辑结构 D．运算实现 （3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。 A．数据具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 （4）以下说确的是（）。 A．数据元素是数据的最小单位 B．数据项是数据的基本单位 C．数据结构是带有结构的各数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 （5）以下与数据的存储结构无关的术语是（）。 A．顺序队列 B. 链表 C.有序表 D. 链栈（6）以下数据结构中，（）是非线性数据结构 A．树 B．字符串 C．队 D．栈 6．试分析下面各程序段的时间复杂度。 （1）x=90; y=100; while(y>0) if(x>100) {x=x-10;y--;} else x++; （2）for (i=0; i 数据库逻辑存储结构 数据库的物理存储结构对应一系列的物理文件,这部分主要描述的是数据存储的实际位置,不过数据如果存储,是以什么结构存储到数据文件中,则取决于数据库的逻辑存储结构. Oracle数据库在执行操作时,并不是以数据文件为单位,而是从逻辑上定义出一组结构,操作的数据可以一步步细分不同的存储单元,oracle 操作数据的过程,实际上就是对这些不同级别的存储单元进行维护和管理的过程. --数据库的存储结构分为:段(segment).区(extent)和数据块(block) 段(segment):段是数据库内占用空间的对象.它们使用数据库中数据文件内的空间.一个tablespace对应多个segment,一个segment只能对 应一个tablespace,但可以跨越对应tablespace下的datafiles --段类型: ●表(table):是数据库中最重要的段,也是数据库内存储数据的最常用方法.表段用于存储非集簇且未分区的表中的数据.表段中的所有 数据都必需存储在一个表空间内. ●表分区(table partition):当一个表的规模很大,且并发操作非常频繁时,可以把这样表划分成若干个分区(partition).而每个分区 驻留在不同的表空间.每个分区的存储参数都可以单独定义.可以通过把每个分区放在不同磁盘上以提高并行操作的能力,从而达到改进系统效率的目的.对于分区表,当一个分区损坏了并不影响其他分区的操作. 提示:要使用分区表,必需使用oracle的企业版分区表的选项(partitioning),oracle提供了大批专门命令来管理和操作分区表. ●簇(cluster):簇与表一样,是一种数据段类型.簇内的行是基于键列值存储的.一个簇可以包含一个或多个表.一个簇的表属于同一个 段并且共享相同的存储特性.可以通过索引或者三列算法来访问集簇表内的行. 提示:簇少用,这样可以减少管理和维护的负担,也可以使跨IT平台的移植变的更加容易. ●索引(index):索引段的目的是加快基于某一特殊(索引关键字)的查询速度,这样查询可以很快查找到某一个表中所需数据的准确位置. 一个特定索引的所有索引记录都记录在一个索引段中.如在吗 果一个表有三个索引,那么就会有三个对应的索引段, SQL> conn erm/erm Connected. SQL> select * from tab; no rows selected SQL> select segment_name,segment_type from user_segments; <==使用user_segments视图查看段类型(segment_type) no rows selected SQL> create table t (id int primary key,name char(10)); <== 此表里有一个主键,建立主键自动创建索引. Table created. SQL> select segment_name,segment_type from user_segments; SEGMENT_NAME SEGMENT_TYPE ------------------------------ --------------- SYS_C005144 INDEX <==t表主键的索引段 T TABLE ●索引分区(index partition):当在一个大型或超大型表上创建索引时,那这个索引也可能很大,所以也可以像分区表一样,将该索引划 分为若干个分区,每个索引分区为一单独的段.这样一个索引可以分布在不同的表空间上.但每个索引分区(段)只能存放在一个表空间中. 第六章数据结构基础 一、选择题 1．下列数据结构中，（C）不是数据逻辑结构。 A.树结构 B.线性表结构 C.存储器物理结构 D.二叉树 2．数据结构是（D）。 A.一种数据类型 B.数据的存储结构 C.一组性质相同的数据元素的结合 D.相互之间存在一种或多种特定关系的数据元素的集合 3.下列关于队列的叙述中，正确的是（C）。 A.在队列中只能入数据 B.在队列中只能删除数据 C.队列是先进先出的线性表 D.队列是后进先出的线性表 4.如果进栈序列为a1，a2，a3，a4，则可能的出栈序列是（B） A.a3，a1，a4，a2 B.a2，a4，a3，a1 C.a3，a4，a1，a2 D.任意顺序 5.链表不具备的特点是（A） A.可能随机访问任意一个节点 B.插入和删除不需要移动任何元素 C.不必事先估计存储空间 D.所需空间与其长度成正比、 6.已知某二叉树的后续遍历序列是DACBE，中序遍历序列是DEBAC， 则它的前序遍历序列是（D）。 A.ACBED B.DEABC C.DECAB D.EDBCA 7.某二叉树中度为2的结点有18个，则该二叉树中有（C）个叶子结点。 A.17 B.18 C.19 D.20 二、填空题 1.数据元素是（数据）的基本单位，是对一个客观实体的数据描述。 2.简单地说，数据结构是指数据之间的（逻辑关系），即数据的逻辑结构。 3.数据的逻辑结构可用一个二元B=（K,R）来表示,其中K表示（数据元素集合），R表示（数据元素之间的前后关系）。 4.数据元素之间的关系有4种基本的存储表示方法，即（集合）、（线性结构）、（树）和（图）。 5.数据的运算中，（移位）是一个很重要的运算过程，插入、删除、修改和排序都包含着这种运算。 6.线性表是一种最简单、最常用的数据结构，通常一个线性表是由n 个性质相同的数据元素组成的（有限序列），其长度即线性表中元素的个数n,当n=0时，称为（空表）。 7.线性表是一种（线性）结构。 8.如果线性表中最常用的操作是存取第i个元素及其前驱的值，则采用（双向链表）存储方式节省时间。 9.线性表的两种存储结构中，（顺序存储结构）的存储密度较大，（链 ◆数据：指能够被计算机识别、存储和加工处理的信息载体。 ◆数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。 ◆数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。 ◆数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。 ◆逻辑结构：指各数据元素之间的逻辑关系。 ◆存储结构：就是数据的逻辑结构用计算机语言的实现。 ◆线性结构：数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。 ◆非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。 比如一个表(数据库)，我们就称它为一个数据结构，它由很多记录(数据元素)组成，每个元素又包括很多字段(数据项)组成。那么这张表的逻辑结构是怎么样的呢? 我们分析数据结构都是从结点(其实也就是元素、记录、顶点，虽然在各种情况下所用名字不同，但说的是同一个东东)之间的关系来分析的，对于这个表中的任一个记录(结点)，它只有一个直接前趋，只有一个直接后继(前趋后继就是前相邻后相邻的意思)，整个表只有一个开始结点和一个终端结点，那我们知道了这些关系就能明白这个表的逻辑结构了。 而存储结构则是指用计算机语言如何表示结点之间的这种关系。如上面的表，在计算机语言中描述为连续存放在一片内存单元中，还是随机的存放在内存中再用指针把它们链接在一起，这两种表示法就成为两种不同的存储结构。(注意，在本课程里，我们只在高级语言的层次上讨论存储结构。) 第三个概念就是对数据的运算，比如一张表格，我们需要进行查找，增加，修改，删除记录 表空间是数据库中最大的逻辑存储单位,同时也是直接与数据库物理结构相关联的逻辑单位,每个表空间都是有一个或多个(最多不超过1023个)数据文件组成. 数据库中创建的对象都保存在指定的表空间中,甚至一个对象可能存在于多个表空间(参考段相关内容进行理解) Oracle将数据逻辑地存放在表空间里,而物理存放在数据文件里,表空间在任何一个时刻都只能属于一个数据库,一个数据库一般有多个表空间,每个表空间都由一个或多个操作系统的数据文件组成.但是一个操作系统的数据文件只能属于一个表空间 提示:10g版本中新引入的一个BIGFILE(big文件)的表空间类型,可以在创建表空间时指定,BIGFILE表空间只能包含一个数据文件或临时文件,不过该数据文件最大能够支持4G(2的32次方)个数据块即使当前数据库的块大小为2KB,该表空间也能拥有8TB的存储空间,如果将数据库的块大小设置为32KB则该表空间最大能达到128TB(如果不考虑文件系统中单个文件最大空间的限制) 在默认情况下创建的表空间是SMALLFILE(小文件)表空间,这一类表空间最多能够拥有1022个数据文件,单个数据文件最大拥有0.4G(2的22次方)个数据块,如果将数据库的块大小设置为32KB,则对于SMALLFILE的表空间类型,最大也将接近128TB(同样如果不考虑文件系统中单个文件最大空间的限制),比BIGFILE类型略小. --创建大文件表空间 SQL> create bigfile tablespace t1 2 datafile 3 '/u01/tablespace/t1.dbf' size 100m autoextend on; Tablespace created. SQL> bigfile关键字表示创建的表空间是一个大文件表空间 datafile指定这个表空间的路径和组成这个表空间的数据文件 size指定这个大表空间的大小 autoextend on表示允许该大文件不够用时自动增长 表空间类型 为加强控制和方便维护,DBA创建表空间时,oracle识别两种类型的表空间 系统表空间(SYSTEM)与非系统表空间 SYSTEM表空间: 随数据库一起创建 所有数据库均需要system 系统表空间中存有数据字典 系统表空间还包含了系统还原(回滚)段 虽然在系统表空间中可以存放用户数据,但考虑到oracle系统的效率和管理上的方便,在系统表空间上不应该存放任何用户数据. 非系统表空间 非系统表空间(non-system)可以有数据库管理员手工创建,支持灵活的管理数据 习题一 一、选择题 1、数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的（B）和运算的学科。 A．结构B．关系C．运算D．算法 2、在数据结构中，从逻辑上可以把数据结构分成（C）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．逻辑结构和存储结构 3、线性表的逻辑顺序和存储顺序总是一致的，这种说法（B）。树形 A．正确B．不正确C．无法确定D．以上答案都不对 4、算法分析的目的是（C）。 A．找出算法的合理性B．研究算法的输人与输出关系 C．分析算法的有效性以求改进D．分析算法的易懂性 二、填空题 1、__数据___是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储、加工和处理，___数据_____是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。例如，数学中所用到的整数和实数，文本编辑所用到的字符串等。 2、数据元素是数据的__基本单位_，有些情况下也称为元素、结点、顶点、记录等。 3、__数据项__是数据不可分割的最小单元，是具有独立含义的最小标识单位。例如构成一个数据元素的字段、域、属性等都可称之为__数据项_。 4、简而言之，数据结构是数据之间的__相互关系_，即数据的_组织关系_。 5、数据的逻辑结构是指数据之间的_逻辑关系_。逻辑结构是从_逻辑关系_上描述数据，它与具体存储无关，是独立于计算机的。因此逻辑结构可以看作是从具体问题抽象出来的_数学模型_。 6、数据的__存储结构_指数据元素及其关系在计算机存储器内的表示。__存储结构_是逻辑结构在计算机里的实现，也称之为映像。 _数据的运算__是指对数据施加的操作。它定义在数据的逻辑结构之上，每种逻辑结构都有一个__数据的运算___。常用的有：查找、排序、插人、删除、更新等操作。 8、数据逻辑结构可以分为四种基本的类型，_集合_结构中的元素除了仅仅只是同属于一个___集合__，不存在什么关系。 9、数据逻辑结构的四种基本类型中，_线性结构_中的元素是一种一对一的关系，这种结构的特征是：若结构是非空集，则有且只有一个开始结点和一个终端结点，并且所有结点最多只能有一个直接前驱和一个直接后继。 10、数据逻辑结构的四种基本类型中，__树型结构_中的元素是一种一对多的关系。 11、图型结构或图状结构是一种__多对多__的关系。在这种逻辑结构中，所有结点均可以有多个前驱和多个后继。 12、有时也可将树型结构、集合和图型结构称为__非线性结构_，这样数据的逻辑结构就可以分为_线性结构_和__非线性结构__两大类。 13、__顺序存储__方式是指逻辑上相邻的结点被存储到物理上也相邻的存储单元中。这种存储结构只存储结点的数值，不存储结点之间的关系，结点之间的关系是通过存储单元的相邻关系隐含的表示出来的。 14、_链接存储_方式是种存储方法，不要求逻辑上相邻的结点在物理上也相邻，即数据元素可以存储在任意的位置上。 _稠密索引_和__稀疏索引_。若每个结点在索引表中都有 数据结构第1章习题参考答案 一、选择题 二、填空题 1、数据元素 2、逻辑结构、存储结构、算法 3、一对一、一对多、多对多 4、有穷性、确定性、可行性、输入、输出 5、 6、 7、集合结构、线性结构、树型结构、图型结构 8、顺序存储、随机存储、索引存储、散列存储 9、 10、 三、简答题 1、简述数据与数据元素的关系与区别。 数据是信息的载体，是对信息的一种符号表示。它能被计算机识别、存储和加工。数据是一个集合。 数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。数据元素是数据集合中的一个成员。 2、简述数据、数据元素、数据类型、数据结构、存储结构、线性结构、非线性结构的概念。 数据是信息的载体，是对信息的一种符号表示。它能被计算机识别、存储和加工。 数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。数据元素可以由一个或多个数据项构成。 数据类型是一组性质相同的值的集合以及定义在这个值集合上的一组操作的总称。 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。数据结构主要研究三个方面的内容：数据的逻辑结构、数据的存储结构和数据的算法。数据结构有时也泛指逻辑结构，反映数据之间的逻辑关系。逻辑结构包括线性结构和非线性结构两大类。 存储结构反映数据元素及其关系在计算机存储器内的表示。 线性结构中的数据元素之间存在一对一的关系。 非线性结构中的数据元素之间存在一对多或多对多的关系。 3、说出数据结构中的4类基本逻辑结构，并说明哪种关系最简单、哪种关系最复杂。 数据结构中的4类基本逻辑结构是集合、线性结构、树型结构和图型结构。集合结构数据元素之间的关系最简单，图型结构数据元素之间的关系最复杂。4、逻辑结构、存储结构各有哪几种？ 逻辑结构分为线性结构和非线性结构两大类。具体包括：集合、线性结构、树型结构和图型结构。 存储结构分为顺序存储结构、链式存储结构、索引存储结构和散列存储结构。 5、简述顺序存储结构与链式存储结构在表示数据元素之间关系上的主要区别。 顺序存储结构是将数据元素按其相互之间的逻辑关系存放在一块连续的存储空间内，由数据元素的存储位置体现数据元素之间的逻辑关系。 链式存储结构中的数据元素不要求存放在一块连续的存储空间内，数据元素之间的逻辑关系与存储位置没有一一对应的关系，数据元素之间的逻辑关系依靠附加在存储数据元素的结点中的指针来表示。 第六章树和二叉树（下载后用阅读版式视图或web版式可以看清） 习题 一、选择题 1．有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最适合的数据结构为( )。 A.向量 B.树C图 D.二叉树 2．树最合适用来表示( )。 A.有序数据元素 B元素之间具有分支层次关系的数据 C无序数据元素 D.元素之间无联系的数据 3．树B的层号表示为la，2b，3d，3e，2c，对应于下面选择的( )。 A. la (2b (3d,3e),2c) B. a(b(D,e),c) C. a(b(d,e),c) D. a(b,d(e),c) 4.高度为h的完全二叉树至少有( )个结点，至多有( )个结点。 A. 2h_l B.h C．2h-1 D. 2h 5.在一棵完全二叉树中，若编号为f的结点存在右孩子，则右子结点的编号为( )。 A. 2i B. 2i-l C. 2i+l D. 2i+2 6.一棵二叉树的广义表表示为a(b(c)，d(e(，g(h))，f))，则该二叉树的高度为( )。 A.3 B.4 C.5 D.6 7.深度为5的二叉树至多有( )个结点。 A. 31 B. 32 C. 16 D. 10 8.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为( )个。 A. 15 B. 16 C. 17 D. 47 9.题图6-1中，( )是完全二叉树，( )是满二叉树。 10.在题图6-2所示的二叉树中： (1)A结点是 A.叶结点 B根结点但不是分支结点 C根结点也是分支结点 D.分支结点但不是根结点 (2)J结点是 A.叶结点 B．根结点但不是分支结点 C根结点也是分支结点 D.分支结点但不是根结点 (3)F结点的兄弟结点是 A.E B.D C．空 D.I (4)F结点的双亲结点是 A.A B.B C.C D.D (5)树的深度为 A.1 B.2 C.3 D.4 (6)B结点的深度为 A.1 B.2 C.3 D.4 (7)A结点所在的层是 A.1 B.2 C.3 D.4 11.在一棵具有35个结点的完全二叉树中，该树的深度为( )。 A.5 B.6 C.7 D.8 12. 一棵有124个叶结点的完全二叉树，最多有( )个结点。 A．247 B．248 C．249 D．250 13.用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R[1…n]中，结点R[i]若 有左子树，则左子树是结点( )。 A. R[2i+l] B. R[2i] C.R[i/2] D. R[2i-1] 14.在一非空二叉树的中序遍历序列中，根结点的右边( )。 A.只有右子树上的所有结点 B.只有右子树上的部分结点 C.只有左子树上的部分结点 D.只有左子树上的所有结点 15．一棵度为m的树中，有n i个度为1的结点，有n2个度为2的结点……，有n m个度为m的结点，则该树的叶结点数为( )。 A. n1+n2+...+n m B. (m-l) n m+...+n2+1逻辑存储结构-段区块
第六章数据结构基础习题及参考答案
逻辑结构与存储结构
逻辑存储结构-表空间
数据结构习题-带答案-12-13-2讲解
数据结构第1章习题参考答案
数据结构课后习题答案第六章doc资料
相关主题
文本预览