## Data Structure Name: B-Trees or Balanced Tree ### Description: - A B-tree data structure is... #flashcard - similar to a [[Binary Search Tree (BST)]], but where there is not only a binary number of branches for each node and each node can hold more than one key. It is structured and sorted similar to a binary search tree, but the additional keys allow for splits between two keys in a node. - There must be a minimum number of keys per node prescribed to a B-tree, which impacts the tree structure and ensure the tree is always balanced. <!--ID: 1751507777604--> ### Variations: - [[Binary Tree]] - [[Binary Search Tree (BST)]] ### Diagram: ![[B-Trees 2024-09-09 14.34.15.excalidraw.svg]] ### General Use: - The goal of using a B-tree is to reduce disk operations. Generally, disk operations are proportional to the height of the tree ## Key Considerations ### Properties: - The rules of B-trees are: - The terminating nodes for the tree (i.e. 'leaves') are all at the same level - The minimum degree of a B-tree is described a *t* and impacts: - Every node must have a minimum of (*t* - 1) keys and am maximum of (2 * *t* - 1) keys - The number of children for a node is the number of keys in the node plus one - All keys in a node are sorted in increasing order - Creating a new node occurs when the number of keys in a node goes above the max ### Strengths - These data structures are optimized for one-dimensional data ### Weaknesses - Conversely to the strength of handling one-dimensional data, multi-dimensional data can have poor performance when using B-trees ### Implementation Details: In this case, *n* is the total number of elements in the B-tree. | | [[Big O - Time Complexity]] | | ------ | --------------------------- | | Access | O(log(n)) | | Add | O(log(n)) | | Delete | O(log(n)) | | Search | O(log(n)) | ### Implementation Tips ## Specific Use Cases - [[Databases]] Systems where there is a large volume of data ## Reference #### Working Notes #### Sources - [Understanding B-Trees: The Data Structure Behind Modern Databases - YouTube](https://www.youtube.com/watch?v=K1a2Bk8NrYQ) - [B-Trees: More Than I Thought I'd Want to Know \| Ben Congdon](https://benjamincongdon.me/blog/2021/08/17/B-Trees-More-Than-I-Thought-Id-Want-to-Know/) #ReadLater