B-Tree of order M is a #202112101956 that has the following Characteristics.
B-Tree could be used in:
- database system
Characteristics
- Root node is either a leaf or has between 2 and M children
- Non-leaf nodes, except root, has between M/2 and M children
- All leaves share the same depth
Details
- Leaves are used to store data
- Keys stored in the left leaves is smaller than the keys stored in the right leaves
- If the leaf is full, it will split the parent node into two
Analysis
- The depth of the B-Tree is at most \(\lceil \log_{\lceil \frac{M}{2} \rceil} N \rceil\)
- Find operation will result in \(O(\log N)\)
- Insertion and Deletion will result in \(O(M \log_M N)\)
- The best choice of M is either 3 or 4
- B-Tree will be 69% full