B Tree Formulas

Posted on 2011-05-08
Last Modified: 2012-05-11
The Problem
g. Suppose that the file is not ordered by the key field Ssn and we want to construct a B+-tree access structure (index on SSn. Calculate (i) the orders p and p_leaf of the B+-tree; (ii) the number of leaf-level blocks needed if if blocks are approximately 69 percent full (rounded up for convenience); (iii) the number of levels needed if internal nodes are also 69 percent full (rounded up for convenience); (iv) the total number of blocks required by the B+-tree; and (v) the number of block accesses needed to search for and retrieve a record from the file - given its Ssn value - using the B+-tree.

h. Repeat part g, but for a B-tree rather than for a B+-tree. Compare your results for the B-tree and for the B+tree.

Formula for order p of a B+ tree:

(p * P) + ((p - 1) * V) < B

Formula for p_leaf of a B+ tree:

(p_leaf * (Pr * V)) + P < B

I'm thinking about part h. Here, I need a formula of some kind for a B tree. Can you help me in some way?
Question by:JCW2
    LVL 76

    Expert Comment

    by:slightwv (䄆 Netminder)
    Unfortunately we are not allowed to provide answers to homework/exam questions.

    Please review:
    LVL 27

    Accepted Solution

    There are masses of analyses for B-Trees (as k-ary trees) on the web, here's one :-

    Incidentally how old is this question? A block size of 512 bytes comes out of the eighties. Today you don't get clusters less than 32K.
    LVL 56

    Expert Comment

    by:Jim Dettman (Microsoft MVP/ EE MVE)
    <<Incidentally how old is this question? A block size of 512 bytes comes out of the eighties. Today you don't get clusters less than 32K. >>

      Disk cluster yes, but many DBMS's operate with blocking other then disk cluster size.  OpenVMS still operates with blocking of 512 bytes to this day for everything.

    LVL 27

    Assisted Solution


    Incidentally the data is only 3.4 Megabytes. It and all possible keys would fit into memory these days.

    Author Closing Comment

    Thank you for your help.

    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    What Security Threats Are You Missing?

    Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

    Displaying an arrayList in a listView using the default adapter is rarely the best solution. To get full control of your display data, and to be able to refresh it after editing, requires the use of a custom adapter.
    Since upgrading to Office 2013 or higher installing the Smart Indenter addin will fail. This article will explain how to install it so it will work regardless of the Office version installed.
    An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
    Video by: Steve
    Using examples as well as descriptions, step through each of the common simple join types, explaining differences in syntax, differences in expected outputs and showing how the queries run along with the actual outputs based upon a simple set of dem…

    779 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    18 Experts available now in Live!

    Get 1:1 Help Now