3-2 优化你的索引-运用二叉查找树

1、二叉树存在 形成 过长的单链表的问题。后面引入平衡二叉树

图：

文：

我们本章的重点这样讲解一下，
只是为了让大家对索引的数据结构呢有一个深刻的印象。
因此我们将通过图的演示去讲解，
代码的话呢，大家可以课下去了解一下，
慕课网也有专门讲解数据结构的经典课程，
面试也会用到的哦。

众所周知，
2叉查找树是每个节点最多有两个子树的数结构。
通常子树被称作左子树或者右子树。
2叉查找树的重要性质是对于树中的每一个节点X，
这里哈，
就是以这个根节点5来做比方，
它的左子树的任意节点的值呢？
均小于X2小于5同时呢，
柚子树上的任意节点的值呢，
均大于X，
也就是大于我们5。
那如果用2叉查找树来作为我们的索引，
确实能够提升查询效率。
这里需要大家注意的是，
我们说的索引的存储块，
和我们之前说的数据库的最小存储单位块或者页，
实际上并非一一对应，
只是为了方便我们的理解呢。
先将其一一对应起来了，
每个存储块存储的是关键字，
还有指向子树的指针。
像这棵树，
它不仅仅是2叉树，
还是平衡二叉树。
那什么是平衡2叉树呢？
就是它的任意一个节点的左子树，
它的高度呢，均不超过1。
那这里我们从根部开始，
根部的左子树呢，
比根部6子树呢，
它的高度呢要