关于思考题二，我想可以有两种方法。
1）平衡的树的保存
那么说明其高度是接近logn的，也就是接近完全二叉树的状态，那么使用数组就能够高效的保存这棵树，即便有些地方会是空的，但是这是以空间换时间，加上数组对缓存友好，保存读取应该都会很快。
保存的时候，首先查看最大的高度，申请一个足够大的数组。然后，从根节点开始，进行遍历，顺序无所谓。重要的是，我们要确定每个节点在数组中的下标，不过很简单，节点i的两个子节点的下标分别是2i+1和2i+2，画个图便清楚了。
还原的时候，首先获取数组第一个节点，构建节点，放入队列中，再使用类似广度遍历的方式，节点出对，在数组中查找其两个子节点，构建并连接两个子节点，子节点入队，直至队列空，构建就完成了。
保存与还原的时间复杂度与空间复杂度都是Ｏ(n)。
2）非平衡的树的保存
情况复杂一点，但是仍然能够使用下标。
保存的时候，为了方便后面的查找和读取，我们访问节点的顺序，是按下标升序的顺序走的，也就是广度遍历的顺序（加入子节点的时候注意先加左节点后右节点（好像本来就是这样的:-D）），这样一来，就能保存一条升序的列表，因而能够使用二分查找的方法寻找子节点的下标。
还原的时候，构建根节点，入队。进入循环，节点出队，使用二分查找的方法找到其两个子节点，构建连接并入队，直至队列为空。
空间复杂度为Ｏ(n)，时间复杂度，保存的是O(n)。还原时，n个节点的遍历需要O(n)，而遍历单个节点需要查找两次数组，因此是O(logn)，总体就是O(nlogn)。
不知有没有更快的方法，大家可以一起讨论下

Redis 数据库介绍
     Redis 中，键的数据类型是字符串，但是值的数据类型有很多，常用的数据类型是：字符串、列表、字典、集合、有序集合

列表（list）
1，列表这种数据类型支持存储一组数据
2，两种实现方法：（1）压缩列表（ziplist）（2）双向循环链表
    * 当列表中存储的数据量比较小时，可以采用压缩列表的方式实现。
    * 具体需要同时满足下面两个条件：
（1）列表中保存的单个数据（可能是字符串类型的）小于 64 字节；
（2）列表中数据个数少于 512 个

3，关于压缩列表
    * 它并不是基础数据结构，而是 Redis 自己设计的一种数据存储结构
    * 类似数组，通过一片连续的内存空间来存储数据
    * 跟数组不同的是它允许存储的数据大小不同

4，压缩列表中的“压缩”如何理解？
    * “压缩”：就是节省内存，之所以说节省内存，是相较于数组的存储思路而言的。数组要求每个元素的大小相同，如果要存储不同长度的字符串，就需要用最大长度的字符串大小作为元素的大小。但压缩数组允许不同的存储空间。

    * 压缩列表这种存储结构，另一方面可以支持不同类型数据的存储
    * 数据存储在一片连续的内存空间，通过键来获取值为列表类型的数据，读取的效率也非常高。

5，不能同时满足压缩列表的两个条件时，列表就要通过双向循环链表来实现

字典（hash）
1，字典类型用来存储一组数据对。
2，每个数据对又包含键值两部分，也有两种实现方式：（1）压缩列表（2）散列表
3，同样，只有当存储的数据量比较小的情况下，Redis 才使用压缩列表来实现字典类型。具体需要满足两个条件：

（1）字典中保存的键和值的大小都要小于 64 字节
（2）字典中键值对的个数要小于 512 个

4，当不能同时满足上面两个条件的时候，Redis 就使用散列表来实现字典类型
    * Redis 使用MurmurHash2这种运行速度快、随机性好的哈希算法作为哈希函数
    * 对于哈希冲突问题，Redis 使用链表法来解决
    * 除此之外，Redis 还支持散列表的动态扩容、缩容。

当数据动态增加，装载因子会不停地变大。为了避免散列表性能的下降，当装载因子大于 1 的时候，Redis 会触发扩容，将散列表扩大为原来大小的 2 倍左右（具体值需要计算才能得到）。

当数据动态减少之后，为了节省内存，当装载因子小于 0.1 的时候，Redis 就会触发缩容，缩小为字典中数据个数的大约 2 倍大小（这个值也是计算得到的）

扩容缩容要做大量的数据搬移和哈希值的重新计算，比较耗时。针对这个问题，Redis 使用渐进式扩容缩容策略：将数据的搬移分批进行，避免了大量数据一次性搬移导致的服务停顿。

集合（set）
1，集合这种数据类型用来存储一组不重复的数据
2，这种数据类型也有两种实现方法：（1）有序数组（2）散列表
3，Redis 若采用有序数组，要同时满足下面这样两个条件：

（1）存储的数据都是整数；
（2）存储的数据元素个数不超过 512 个。
当不能同时满足这两个条件的时候，Redis 就使用散列表来存储集合中的数据。
有序集合（sortedset）
1，它用来存储一组数据，并且每个数据会附带一个得分。通过得分的大小，将数据组织成跳表这样的数据结构，以支持快速地按照得分值、得分区间获取数据。
2，当数据量比较小的时候，Redis 可用压缩列表来实现有序集合。使用的前提有两个：

（1）所有数据的大小都要小于 64 字节；
（2）元素个数要小于 128 个
数据结构持久化
1，尽管 Redis 经常会被用作内存数据库，但它也支持将内存中的数据存储到硬盘中。当机器断电的时，存储在 Redis 中的数据不会丢失

Redis 的数据格式由“键”和“值”两部分组成。而“值”又支持很多数据类型，像字典、集合等类型，底层用到了散列表，散列表中有指针的概念，而指针指向的是内存中的存储地址。

Redis 是如何将一个跟具体内存地址有关的数据结构存储到磁盘中的？
1，Redis 遇到的这个问题被称为数据结构的持久化问题，或者对象的持久化问题
2，将数据结构持久化到硬盘主要有两种解决思路：
    * 第一种是清除原有的存储结构，只将数据存储到磁盘中。
        （1）当需要从磁盘还原数据到内存时，再重新将数据组织成原来的数据结构。Redis 采用的就是这种持久化思路。
        （2） 这种方式有一定的弊端：数据从硬盘还原到内存的过程，会耗用比较多的时间
        
    * 第二种方式是保留原来的存储格式，将数据按照原有的格式存储在磁盘中