B树与B+树

B树与B+树的区别

总：B树和B+树都是属于一种自平衡的多叉树，每个节点可以包含多个子节点，树高较低，整体呈现一种矮胖型，另外它们I/o次数少，查询效率较高

分：它们的区别在于B树是把数据储存在所有的节点中，包括内部节点；而B+树是把数据存在叶子节点中，并且所有叶子节点通过有序的链表相连，内部节点只储存索引，另外MySQL还对B+树进行了优化，它将B+树的叶子节点改成了数据页，数据页上面锥的是有序链表，数据页之间使用的是双向指针，每个数据页中可以放16KB的数据，查询数据是用的二分查找。

MySQL为什么不用红黑树和二叉树

二叉树和红黑树都属于二叉树，对于数据较多时，树高较高，磁盘进行IO操作时会耗费大量时间和资源，另外红黑树还属于平衡二叉树，在对数据进行插入、删除时，还需要，消耗资源也比较多，相比B+树，B+树能更好的提供数据访问的效率，更适合处理大规模的数据需求，并且B+树更好的进行范围查询，另外B+树实现了聚集索引，数据和索引放在一起，查询效率高

红黑树

效率稳定：O（log（n））

性质

• 二叉搜索树（左节点<根节点<右节点）（左根右）
• 根和叶子节点（Null）都是黑色的（根叶黑）
• 不存在连续的两个红色节点（不红红）
• 任一节点到叶子结点所有路径中黑节点数量相同（黑路同）

插入：插入的节点默认是红色节点，因为插入红色节点要比插入黑色节点对红黑树的影响要小

红黑树.png