通俗易懂的图文 红黑树,B树,B+树 本质区别及应用场景

在这里总结一下这篇图文。

  1. 用SpringBoot做了一个学生管理系统，这个项目前端用的 React+Webpack，后端用的 Nginx+Spring Boot+Redis+MySQL，前后端是分离的，最后用 Docker 进行容器化部署。主要模块有师生系统、课程系统、成绩系统、选课系统等。
  2. 底层 MySQL 是存储，Redis 是缓存，Dao 层操作 MySQL，Cache层操作 Redis，Service 层处理业务逻辑，Rest API 层为前端提供 Rest 接口。前端这边用 React 进行模块化，Webpack 打包部署。网关 Nginx 进行负载均衡。MySQL、Redis、Nginx 和 Spring Boot 应用都放在 Docker 里部署。
  3. 使用Redis是为了选课系统的高并发考虑，要测试整个系统可以抗住多大的并发量。
  4. 数据库查询慢，使用索引，索引的数据结构是 B+树，复杂度logn，hash方式复杂度 o1， 为什么在数据库中索引的数据结构不使用hash而用B+树呢？
  5. 为什么 MySQL 数据库要用 B+ 树存储索引?
  6. 项目中用到的技术，一定要多看看原理，特别是能和数据结构和算法挂钩的那部分。
  7. 红黑树是平衡树的一种，本质上都是为了保证树不退化……有着复杂的插入规则和删除规则。
    红黑树的特性:
    （1）每个节点或者是黑色，或者是红色。
    （2）根节点是黑色。
    （3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
    （4）如果一个节点是红色的，则它的子节点必须是黑色的。
    （5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
  8. 图片说明
  9. 文件系统和数据库的索引都是存在硬盘上的，并且如果数据量大的话，不一定能一次性加载到内存中。

图片说明

图片说明
图片说明
图片说明
这也是和业务场景相关的，你想想，数据库中 Select 数据，不一定只选一条，很多时候会选多条，比如按照 ID 排序后选 10 条。
图片说明
我明白了，如果是多条的话，B 树需要做局部的中序遍历，可能要跨层访问。而 B+ 树由于所有数据都在叶子结点，不用跨层，同时由于有链表结构，只需要找到首尾，通过链表就能把所有数据取出来了。

这和业务场景有关。如果只选一个数据，那确实是 Hash 更快。但是数据库中经常会选择多条，这时候由于 B+ 树索引有序，并且又有链表相连，它的查询效率比 Hash 就快很多了。而且数据库中的索引一般是在磁盘上，数据量大的情况可能无法一次装入内存，B+ 树的设计可以允许数据分批加载，同时树的高度较低，提高查找效率。

2-3树，2-3-4树，红黑树。
从二叉树出发，一路经过二叉查找树、平衡树、AVL树、2-3树、2-3-4树、B树，最后终于得出了红黑树的本质，红黑树的本质就是一颗2-3-4树，换了个皮肤而已。
你对红黑树真的了解吗?

R树是B树在高维空间的扩展，是一棵平衡树。