Explain why the time needed to do a typical B-tree operation

Assignment Help Computer Engineering

Reference no: EM131851215

Problem

1. If a key in a B-tree is not in a leaf, prove that both its immediate predecessor and immediate successor (under the natural order) are in leaves.

2. Suppose that disk hardware allows us to choose the size of a disk record any way we wish, but that the time it takes to read a record from the disk is a+bd, disk accesses where a and b are constants and d is the order of the B-tree. (One node in the B-tree is stored as one record on the disk.) Let n be the number of entries in the B-tree. Assume for simplicity that all the nodes in the B-tree are full (each node contains d - 1 entries).

(a) Explain why the time needed to do a typical B-tree operation (searching or insertion, for example) is approximately (a + bd)logd n.

(b) Show that the time needed is minimized when the value of d satisfies d(ln d-1)= a/b. (Note that the answer does not depend on the number n of entries in the B-tree.)

(c) Suppose a is 20 milliseconds and b is 0.1 millisecond. (The records are very short.) Find the value of d (approximately) that minimizes the time.

(d) Suppose a is 20 milliseconds and b is 10 milliseconds. (The records are longer.) Find the value of d (approximately) that minimizes the time.

Reference no: EM131851215

Questions Cloud

What is talent management : How would you do a complete background investigation on applicants to minimize concerns about negligent hiring?

What is the single most important leadership behavior : What is the single most important leadership behavior lacking in the organization and how is it negatively affecting employees?

Prepare net-present-value analysis of proposed long runway : Prepare a net-present-value analysis of the proposed long runway.

Write a method that will traverse a linked B-tree : Write a method that will traverse a linked B-tree, visiting all its entries in order traversal of keys (smaller keys first).

Explain why the time needed to do a typical B-tree operation : Explain why the time needed to do a typical B-tree operation (searching or insertion, for example) is approximately (a + bd)logd n.

How much should you be willing to pay for bond : Bond valuation Bond X is noncallable and has 20 years to maturity, 10% annual coupon and $1,000 par value. How much should you be willing to pay for Bond today.

How did welch motivate and inspire employees : Synthesize the following in your analysis of this case study relative to the second ten years that Welch was at the helm of GE.

What is the smallest number of entries : What is the smallest number of entries that, when inserted in an appropriate order, will force a B-tree of order 5 to have height 3 (that is, 3 levels)?

Determine project after-tax cash flows for time zero : Assuming a 40% effective federal and state income tax rate, determine project after-tax cash flows for time zero.

User Account

All Pages