B Tree/ Balanced Tree/ B+ Tree

✅ B Tree

self-balancing tree
균형이 맞는 트리 ➡️ efficient in searching
all leaf nodes are at the same level
🆚 can have multiple children than binary tree(more than two)

💡 Applications

• databases to store indexes for efficient searching, retrival
• DNS servers: store domain names
• File System

💡 Rules

• Balanced: all leaf nodes are at the same level
  • time to access data remains constant
• Self-balancing: as new data is inserted, deleted, tree automatically adjusts to maintain balance
• Multiple keys per node
• Ordered: nodes should be sorted
• number of keys n, then number of children node must be n+1
• root node should have min 2 child nodes
• other nodes should have more than M/2 nodes
• same distance to outer node
• no duplication of node

💡 Reference

https://www.geeksforgeeks.org/introduction-of-b-tree-2/

✅ B+ Tree

data pointers are stored only at the leaf nodes of the tree

• stored as index node + leaf node
• leaf node is connected, allowing search efficiency
• used in big database

🆚 B Tree

https://www.geeksforgeeks.org/introduction-of-b-tree/?ref=lbp