DBMS - B-Trees

Question 1

Tree

Answer 1

Data structure whose components are a set of nodes and edges. Each node has values, each edge connects two nodes.

Question 2

Binary Tree

Answer 2

Directed edge (i.e child to parent), each child has only one parent, each node is either a parent of one or two nodes or a leaf. The root has no parents.

Question 3

Search Tree Properties

Answer 3

• Always one more pointer than keys
• Each key value represents an indexing key
• Each non-null pointer refers to a sub-tree of node structures.

Question 4

Structure of Binary Search Tree

Answer 4

Two pointers, one key value

Question 5

B-Tree structure

Answer 5

Large number of pointers and keys in a node. The values of ki in a page are ordered. Duplicate key values are allowed.

Question 6

Strict data structure and data placement leads to

Answer 6

overflows

Question 7

Requirements and Issues of Tree

Answer 7

• Balance
• Leafs must be on same level
• Block Based
• Allow direct and sequential reads
• High space utilisation per block
• Resilient to some abuse
• Activities have similar cost basis
• Sharing mechanism is possible and reasonable

Question 8

Why do we use B-Trees over BSTs

Answer 8

Can choose to build trees from bottom up instead of top down. Allow better root to emerge from the key’s parent while keeping the structure balanced.

Question 9

B-Trees and Paging

Answer 9

B-Trees are perfect for paging. Performance enhanced when root page is kept in ultra fast memory storage.

Question 10

B-Trees Computational Requirement

Answer 10

Deterministic side
- Can work out index size and no. of levels given no. of keys and page size.
- Can work out min/max time to compute operations over B-Tree index data structure.

Question 11

Order (in B-Tree)

Answer 11

Maximum number of descendants a node or page should have

Question 12

Root (in B-Tree)

Answer 12

First page to read and where first multi-way split. Higher order = more partitions possible.

Question 13

Leaves (In B-Tree)

Answer 13

Are the pages at the lowest level of the B-Tree, with no descendants?

Question 14

B-Tree Properties for an M-Order Tree

Answer 14

1) Every page has a maximum of M descendants
2) Root has at least 2 descendants unless its a leaf
3) All leaves are on same level
4) A nonleaf page with k descendants contains k-1 keys
5) A leaf page has at least (ceiling(m/2)-1) keys and not more than m-1 keys
6)Every page beside root and leaves has at least ceiling(m/2).
7) Any keys present in a page are in order
8) For all search keys of value X in sub-tree pointed by P: Ki-1<xKi for 1<q, x<Ki for i=1, Ki-1<x for i=q

Question 15

B-Trees

Answer 15

• Balanced
• Shallow and require less disk reads as traversal is short
• Random inserts/deletes accommodated at reasonable and predictable cost
• At least load 50% use of claimed space - average 66%
• Sequential search not implicit but possible
• Flexible to accommodate non-key search field values

Question 16

Searching

Answer 16

Efficient as each page is a multi-way discriminator (at best order m). Could be implemented by reading a block into single main memory buffer.

Question 17

Insertion + Splitting

Answer 17

Relatively involved procedure, especially when page becomes saturated and needs to be split into two pages with the medium key promoted.

Promoted key might entail other splits recursively.

Small number of disk pages need to be concurrently read into main memory and at worst there can be as many writes as tree depth.

Question 18

Deletion

Answer 18

If non leaf key must be pages, the next key must raise to fill the gap. If a page’s key count is below acceptable level, then re-grouping to the preceding page must happen.

Small number of pages must be read concurrently into main memory

Question 19

Number of writes in delete

Answer 19

= number of inserts

Question 20

All Split and Promote Operations

Answer 20

Searching, Insert+Splitting and Deletion all take O(logn m) time in worst case.

Given B-Tree order m with n keys.

Question 21

Observation 1 (Operations)

Answer 21

Number of descendants a certain tree level has is equal to number of keys present in that level and all other higher levels + 1.

Question 22

Observation 2 (Operations)

Answer 22

Minimum number of descendants that any level can have; permutation yields a B-Tree that has max height and min breadth.

Specifically: - Root Page has 2 as min
- 2nd level has ceiling(m/2) per page i.e 2.
- The nth level has ceiling(m/2)^(d-1)*2

Question 23

Create Index in Postgres

Answer 23

CREATE Table emp(…) ;
CREATE INDEX idx_emp_job ON emp(job);
CREATE INDEX idx_emp_deptno_job ON emp(deptno,job);

Question 24

Index Selection Issues

Answer 24

Indexes help if lots of data present even in non-key fields. Indexes need updating.