现在，我们可以轻松的得到两个表达式树的大小关系，就可以像之前谈到的那样，构造一个排序的线性表，并且使用二分法进行查询，这样查询性能便可以控制在O(log(n))了。不过我们在这里选择二叉搜索树（Binary Search Tree，BST）这种数据结构进行存储，如下：
上图来自Wikipedia，它很好地展现了二叉搜索树这种数据结构的存储方式。二叉搜索树查询操作的时间复杂度是O(h)，其中h是树的高度。所以在极端情况下，二叉搜索树会发生“退化”，使查询操作的时间复杂度变成（或接近）O(n)，如下：
上图来自Wikipedia，它很好地展现了二叉搜索树这种数据结构的存储方式。二叉搜索树查询操作的时间复杂度是O(h)，其中h是树的高度。所以在极端情况下，二叉搜索树会发生“退化”，使查询操作的时间复杂度变成（或接近）O(n)，如下：
其实老赵选择二叉搜索树作为存储数据结构的原因有些可笑，那只是因为.NET Framework的类库中已经提供了现成的实现，那就是SortedList（及对应的范型类）。SortedList的实现便是一棵二叉搜索树（是不是AVL树不清楚，MSDN上提到了查询性能为O(log(n))，并没有提到“退化”，但也没有提到自动平衡，因此有机会还是看看它的代码吧）。SortedList<TKey, TValue>还能够接受一个IComparer<TKey>类型的对象用于自定义比较方式，使用起来简直太容易了。因此，我们就以此实现一个SortedListCache：
public class SortedListCache<T> : IExpressionCache<T> where T : class
{
private ReaderWriterLockSlim m_rwLock = new ReaderWriterLockSlim();
private SortedList<Expression, T> m_storage = new SortedList<Expression, T>(
new ExpressionComparer());
public T Get(Expression key, Func<Expression, T> creator)
{
T value;
this.m_rwLock.EnterReadLock();
try
{
if (this.m_storage.TryGetValue(key, out value))
{
return value;
}
}
finally
{
this.m_rwLock.ExitReadLock();
}
this.m_rwLock.EnterWriteLock();
try
{
if (this.m_storage.TryGetValue(key, out value))
{
return value;
}
value = creator(key);
this.m_storage.Add(key, value);
return value;
}
finally
{
this.m_rwLock.ExitWriteLock();
}
}
}
由于一次表达式树的比较操作其时间复杂度为O(m)，而二叉搜索树的查询操作其时间复杂度是O(log(n))，即进行O(log(n))次比较。因此SortedListCache的查找操作，最坏情况下其时间复杂度为O(m * log(n))——这可比前两次提到的SimpleKeyCache和PrefixTreeCache的O(m)时间复杂度要差啊。说得没错，理论上的确是这样的。不过还是需要提一下，理论和实际是有差别的，就目前的问题来说：
ExpressionComparer非常高效，在一般情况下很少会需要比较完整的遍历序列，再由于它不需要任何的字符串拼接或新对象的创建，因此其性能并不如想象中低。
对于O(log(n))这个时间复杂度来说，由于n为缓存容器中对象数目，就算再大，被以2为底取对数之后也变得不可怕了——要知道log(1020)也只是约等于55.22，这是个什么规模呢？
但是从理论上来说，O(m * log(n))的时间复杂度还是比O(m)要高，因此性能究竟如何，还要由测试数据说了算——在老赵进行详细比较之前，不如您自己先试试看？
更正：据源码分析，SortedList是文章中所写的排序后的线性表，加上二分查找这样的数据结构（插入删除O(n)，查找O(log(n))），而不是一颗二叉搜索树。事实上，SortedDictionary是使用红黑树（也是一种平衡的二叉搜索树）实现的（插入删除查找都是O(log(n)），兄弟们可以根据情况自行进行选择。犯此错误的原因在于老赵亲信了MSDN的错误描述（见26楼）；更主要的原因也是没有更进一步的思考，虽然发现了MSDN的矛盾之处，但还是简单的写了出来。立此为证，以观后效。
