二叉查找树(BST)
二叉查找树（Binary Search Tree）是一种基于二叉树的数据结构，它具有以下特点：
- 左子树所有节点的值均小于根节点的值。
- 右子树所有节点的值均大于根节点的值。
- 左右子树也分别为二叉查找树。
当二叉查找树是平衡的时候，也就是树的每个节点的左右子树深度相差不超过 1 的时候，查询的时间复杂度为 O(log2(N))，具有比较高的效率。然而，当二叉查找树不平衡时，例如在最坏情况下（有序插入节点），树会退化成线性链表（也被称为斜树），导致查询效率急剧下降，时间复杂退化为 O（N）。
由于树是存储在磁盘中的，访问每个节点，都对应一次磁盘 I/O 操作（假设一个节点的大小「小于」操作系统的最小读写单位块的大小）（实际上InnoDB 里的 B+ 树中的每个节点都是一个数据页，而InnoDB 数据页的默认大小是 16KB），也就是说树的高度就等于每次查询数据时磁盘 IO 操作的次数，所以树的高度越高，就会影响查询性能。
而且会随着插入的元素越多，树的高度也变高，意味着需要磁盘 IO 操作的次数就越多，这样导致查询性能严重下降，再加上不能范围查询，所以不适合作为数据库的索引结构
为了解决这个问题，并提高查询效率，人们发明了多种在二叉查找树基础上的改进型数据结构，如平衡二叉查找树、B-Tree、B+Tree 等。