• 二叉树的每个节点至多有两个子节点(二颗子树),二叉树的子树有左右序之分,次序不能颠倒。
    • 且在二叉树中,左子树的键值永远比右子树的小,并且小于根键值。
    • 二叉树是一种比顺序结构更加高效地查找目标元素的结构,它可以从第一个父节点开始跟目标元素值比较,如果相等则返回当前节点,如果目标元素值小于当前节点,则移动到左侧子节点进行比较,大于的情况则移动到右侧子节点进行比较,反复进行操作最终移动到目标元素节点位置。
    • 缺点:在大部分情况下,我们设计索引时都会在表中提供一个自增整形字段作为建立索引的列,在这种场景下使用二叉树的结构会导致我们的索引总是添加到右侧,在查找记录时跟没加索引的情况是一样的

    二叉树 - 图1