计算机专业英语(霍洪涛)课件Chapter 3

Chapter 2 Data Structure

Review mount v. If you mount an object on something, you fix it there firmly. configure v. If you configure a piece of computer equipment, you set it up so that it is ready for use. Install v. If you install a piece of equipment, you put it somewhere so that it is ready to be used.2

Review 扩充槽 expansion slot system board/motherboard 主板 基本输入/输出系统 basic input/output system(BIOS) 节能模式 power saving mode 插头插座 plug socket 盛行很广的 prevailing take advantage of 利用 衡量标准 metric 分层结构 hierarchy3

Review Why we need cache?

Microprocessors are faster than main memory. Memory access time is increasingly the bottleneck in overall application performance. One way to overcome this problem is to insert a small high-speed buffer memory between the processor and main memory. Such a buffer is generally referred to as cache memory.4

Review Cache hierarchy

It is possible to implement multiple levels of cache memory. Some of these levels will be a part of the microprocessor(they are said to be on-chip), whereas other levels may be external to the chip. To distinguish between these caches, a level notation is used. The higher the level, the farther away the cache is from the CPU.

Unit 1 Balanced Tree Data Structure1. Introduction(P40) Why do we need a balanced tree?When working with large sets of data, a relatively small portion of the data structure is maintained in primary storage(RAM), and additional data is read from secondary storage as needed. Unfortunately, most secondary storage is significantly slower than RAM. 在操作很多组数据的时候，有一小部分的数据结构存 在RAM里，额外的数据在需要的时候从次存储器里面 读取。很不幸的是，大部分的次存储器的速度都比 RAM慢。6

Unit 1 Balanced Tree Data Structure1. Introduction(P40) Why do we need a balanced tree?Balanced trees are optimized for situations when part or entire tree must be maintained in secondary storage. Since disk accesses are expensive operations, a balanced tree tries to minimize the number of disk accesses. B树处理部分或者全部树都必须存储在次存储器 的情况是最优的。因为磁盘存取是很费时的操作 ，B树试图使进出磁盘的次数最少。7

Unit 1 Balanced Tree Data Structure entire 全部的 adj. You use entire when you want to emphasize that you are referring to the whole of something, for example, the whole of a place, time, or population. all 全部的 You use all to indicate that you are referring to the whole of a particular group or thing or to everyone or everything of a particular kind. 例：…the restaurant that Hugh and all his friends go to…8

Unit 1 Balanced Tree Data Structure2. The Structure of Balanced Tree(P40) A. Each node of a balanced tree may have various number of keys and children. B树每一

个结点都可能有多个键和子结点。

Unit 1 Balanced Tree Data Structure2. The Structure of Balanced Tree(P40) B. Each key has an associated child that is theroot of a subtree containing all nodes with keys less than or equal to the key but greater than the preceding key. 每一个键都有一个关联的子结点。这个子结点是分 树的根，包含了所有比这个键小或者相等的键的结 点，但是比前面结点的键大。

Unit 1 Balanced Tree Data Structure2. The Structure of Balanced Tree(P40)C. Each node also has an additional rightmost child that is the root for a subtree containing all keys greater than any keys in the node. 每一个结点都有一个额外的最右边的子结点。这个 子结点是分树的根，包含了所有比这个结点的键大 的键。

Unit 1 Balanced Tree Data Structure3. Operations on Balanced Tree 3.1 Search(P42) After finding the value greater than or equal to the desired value, the child pointer to the immediate left of that value is followed. If all values are less than the desired value, the rightmost child pointer is followed. 找到大于或者等于期望值的值时候，就跟随直接指 向左边的子指针。如果所有值都小于期望值，就跟 随最右子指针。

Unit 1 Balanced Tree Data Structure3. Operations on Balanced Tree 3.1 Create(P42)

The Balanced-Tree-Create operation creates an empty balanced tree by allocating a new root node that has no keys and a leaf node. Balanced-Tree-Create操作通过分配一个没有 键的新的根节点建立了一个空的B树，这是一 个叶节点。

Unit 1 Balanced Tree Data Structure3. Operations on Balanced Tree 3.1 Split(P43)

If node becomes “too full”, it is necessary to perform a split operation. The split operation transforms a full node with 2t-1 keys into two nodes with t-1 keys each. 如果结点“太满”,就有必要执行分离操作。 分离操作将有2t-1个键的满结点转化成两个有t1个键的结点。

Unit 1 Balanced Tree Data Structure3. Operations on Balanced Tree 3.1 Insert(P44)① A appropriate node for the key must be located using an algorithm similar to Balanced-TreeSearch. ② The key must be inserted into the node. If the node is not full prior to the insertion, no special action is required; however, if the node is full, the node must be split to make room for the new key. a. 用Balanced-Tree-Search类似的算法为键定位一个合 适的节点。 b. 这个键必须插入这个结点。如果在插入之前，结点没有 满，就不需要特殊的操作；但是如果结点满了，就需要 分离结点，为新键腾出空间。

Unit 1 Balanced Tree Data Structure Key word predecessor(P40,L1) 前驱，前任 successor (P40,L2 ) 后继，继任 median(P43,L2) 中值 commonplace(P44,RL5) adj.常见的 adj. 足够的 sufficient(P45,P2L5) Corrupt adj.退化