固定长度的数据结构很简单，大家每天都在用。

可变长度数据结构，都可以通过内嵌对象的形式，转化成固定长度的数据结构，大家每天也都在用，例如：

每个 person 对象的长度是固定的，但是，其内嵌的 name 和 address 是变长的。从而，整个对象占据的总空间也是变长的。

但是，将这样的的对象平坦化，使之只占据一块连续空间，使用的人很少，因为在绝大多数情况下，很少有人思考这个问题，并且，大多数问题已经使用内嵌数据结构解决掉了。

然而，如果内存很紧张，或者需要处理得数据量非常大，这种方式浪费的内存就太多了。假定我们现在创建了一个 map<int, person> ，在gcc4.1 的 64位环境中，按8字节对齐，这个 map 总共会占用多少内存呢？

1. sizeof(map) = 48
2. sizeof(string) = 8
3. sizeof(person) = 24
4. sizeof(person_node) = alignto(24 + 32(rbtree node overhead), 8) = 56
5. sizeof(string_node) = 8*3(refcount, size_endptr, capacity_endptr)
6. memsizeof(string) = sizeof(string_node) + alignto(strlen + 1, 8)
7. memsizeof(person_node) = sizeof(person_node) + memsizeof(name) + memsizeof(address)

如果 avg(name) = 10, avg(address) = 20

实际占用的空间，大约还要再加上4：avg(name) = 14, avg(address) = 24

那么 memsizeof(person_node) = 56 + 24*2 + 14 + 24 = 142

那么该map 实际占用空间（gcc 的每个 map 还有一个虚结点:32个字节）：

48+32+n*142 = 80+n*142

如果使用一种理想的变长数据结构，再加上红黑树的优化(none virtual node, compressed color, no parentptr)，需要多少内存呢？

1. sizeof(map) = 16
2. memsizeof(person_node) = alignto(16(treenode) + 4(id) + 2*1(strlen) + 10(name) + 20(address) = 52, 8) = 56

memsizeof(map) = 16 + 56*n

内存一下节省了 60% 还多，也就是说，如果内存大小已经固定，可以装入 2.5 倍的数据。

1. 如果用来做集群缓存，可以节省50%的机器（系统也要占一些内存）。
2. 如果有5.6G的内存可用，就可以装入1亿条数据。
3. 并且，在节省了60%内存的同时，还有另外一种好处：提高cache命中率，如果3个字段访问的频率相同，cpu的 cache miss 会降低3倍。
4. 可以预见，因为cache miss降低，map.find 速度会大幅提高。

这个可变数据结构可以这样设计：

更复杂的情况：

1. 如果nName 和 nAddress 要大于 255 呢？——把 unsigned char 改成 unsigned short, 甚至 unsigned int
2. 如果person的字段很多，例如有20个字段：

这就不光是写代码的复杂了，运行时字段访问的性能也成问题！性能问题可以用另外一种方式——使用直接定位——来解决。

如果需要变长数据的数组，怎么办？简单，offset array + data byte array，具体实现方式与 person4 类似，只不过 offset array 元素需要使用更宽的整数。