Explain leaf of b tree which holds a sublist

Assignment Help Database Management System
Reference no: EM1367457

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: EM1367457

Questions Cloud

Estimate consumer and producer surplus before quota : Estimate aggregate consumer and producer surplus before quota. Estimate new consumer and producer surplus after quota.
Explain specific challenges of facing designer : Explain specific challenges of facing the designer, specifically with regard to limitations of hardware, software and interface design two paragraph each.
Examples of a medical office implementing ehr : Research and provide examples of a medical office that has implemented EHRs. How has it helped them? Has it created any negative aspects.
Determine the growth rate of real gdp : Suppose last year's real GDP was $7,000 billion, this years nominal GDP is $8,820 billion, and GDP-deflator for this year is 120. Determine the growth rate of real GDP?
Explain leaf of b tree which holds a sublist : Artificially small example of B+ tree is shown here (pdf). (Note only part of tree is shown in detail.) What nodes of example B+ tree are visited to find posting list for "dune"?
Illustrate what do you think disrupted mcdonald plans : Within two weeks sales had fallen. Utilizing your knowledge of game theory, Illustrate what do you think disrupted McDonald's plans.
Evidence-based practice report : Identify a research topic that you intend to investigate and write about as an evidence-based practice report Project Topic such as COPD, Asthma, Cancer or other health topics)
Illustrate what is economy aggregate consumption function : Illustrate what is economy's aggregate consumption function. Illustrate what is marginal propensity to consume for economy.
Determine supply and demand for labor : Many factors discuss the supply and demand for labor. Identify and describe two factors that would increase or decrease the demand for labor.

Reviews

Write a Review

Database Management System Questions & Answers

  Knowledge and data warehousing

Design a dimensional model for analysing Purchases for Adventure Works Cycles and implement it as cubes using SQL Server Analysis Services. The AdventureWorks OLTP sample database is the data source for you BI analysis.

  Design a database schema

Design a Database schema

  Entity-relationship diagram

Create an entity-relationship diagram and design accompanying table layout using sound relational modeling practices and concepts.

  Implement a database of courses and students for a school

Implement a database of courses and students for a school.

  Prepare the e-r diagram for the movie database

Energy in the home, personal energy use and home energy efficiency and Efficient use of ‘waste' heat and renewable heat sources

  Design relation schemas for the entire database

Design relation schemas for the entire database.

  Prepare the relational schema for database

Prepare the relational schema for database

  Data modeling and normalization

Data Modeling and Normalization

  Use cases perform a requirements analysis for the case study

Use Cases Perform a requirements analysis for the Case Study

  Knowledge and data warehousing

Knowledge and Data Warehousing

  Stack and queue data structure

Identify and explain the differences between a stack and a queue data structure

  Practice on topic of normalization

Practice on topic of Normalization

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd