B 树相对于平衡二叉树的不同是：每个节点包含的关键字增多了。

• 特别是在 B 树应用到数据库中的时候，数据库充分利用了磁盘块的原理（磁盘数据存储是采用块的形式存储的，每个块的大小为 4K，每次 IO 进行数据读取时，同一个磁盘块的数据可以一次性读取出来）把节点大小限制和充分使用在磁盘快大小范围；
• 把树的节点关键字增多后树的层级比原来的二叉树少了，减少数据查找的次数和复杂度。

简称 BST，也称二叉排序树或二叉查找树。

特点：

• 任一结点 > 其左子树的所有结点，
  并且< 其右子树的所有结点；
• 结点的左、右子树，也是二叉排序树；
• 每个结点键值唯一（不能重复）

重要性质：

• 中序遍历二叉排序树得到递增序列

所以判断 1 棵二叉树是否是二叉排序树？
只要中序遍历，得到递增序列才是。

二叉树遍历主要包括：

• 深度优先遍历
  • 前序遍历（递归法，迭代法）
  • 中序遍历（递归法，迭代法）
  • 后序遍历（递归法，迭代法）
• 广度优先遍历
  • 层次遍历（迭代法）