Estimate the height of the b plus tree

Assignment Help Database Management System

Reference no: EM1364810

Consider an inverted index containing, for each term, the posting list (i.e. the list of documents and occurrences within documents) for that term. The posting lists are accessed through a B+ tree with the terms serving as search keys. Each leaf of the B+ tree holds a sublist of alphabetically consecutive terms, and, with each term, a pointer to the posting list for that term.

Part a. An artificially small example of a B+ tree is shown here (pdf). (Note only part of the tree is shown in detail.) What nodes of the example B+ tree are visited to find the posting list for "dune"?

Part b. Suppose there are 2 million terms for a collection of 32 million documents of total size 200 gigabytes. We would like each internal node of the B+ tree and each leaf of the B+ tree to fit in one 8-kilobyte page of the file system. Recall that a B+ tree has a parameter m called the order of the tree, and each internal node of a B+ tree has between m+1 and 2m+1 children (except the root, which has between 2 and 2m+1). Assume that each term is represented using 16 bytes, and each pointer to a child in the tree or to a posting list is represented using 8 bytes. Find a value for the order m of the B+ tree so that one 8 kilobyte page can be assigned to each internal node and leaf, and so that an internal node will fill, but not overflow, its page when it has 2m+1 children. If you need to make additional assumptions, state what assumptions you are making.

Part c. For your m of Part b, estimate the height of the B+ tree. (Giving a range of heights is fine.) Also estimate the amount of memory needed to store the tree, including leaves but not including the posting lists themselves.

Part d. Estimate the aggregate size of the posting lists.

Reference no: EM1364810

Questions Cloud

Using expected monetary value as decision criterion : Bill Goodman has been offered the opportunity to invest $15,000 in a start-up company that intends to supply personal digital assistants to physicians in order to enable them to determine the approved medication for each HMO patient they treat.

Operations management-jacobs baby food company : Operations Management-Jacob's Baby Food Company - Jacob's Baby Food Company must go through the following steps to make mashed carrots

Explain the electric flux through the surface of the cube : explain the electric flux through the surface of the cube. Calculate the volume charge density of the atmosphere, assuming it to be uniform between 270 and 420 m.

Trends in medical practice in the united states : What do you consider the most important trends in medical practice in the U.S.? Discuss at least three major trends, and provide your assessment as to whether these are positive or negative trends for medical care in our country.

Estimate the height of the b plus tree : Estimate the height of the B+ tree. (Giving a range of heights is fine.) Also estimate the amount of memory needed to store the tree, including leaves but not including the posting lists themselves.

Operations management-oakwood outpatient clinic : Oakwood Outpatient Clinic is analyzing its operation in an effort to improve performance.

Describe the probability section of the risk management plan : Describe the probability and impacts section of the Risk Management Plan and justify the values assigned

Analyze four eras of business : Examine the four eras of business and make a prediction for what the next era will be like. Explain the rationale behind your prediction.

What is the resultant velocity of the motor boat : What is the resultant velocity of the motor boat. What distance downstream does the boat reach opposite shore.

User Account

All Pages