设计一个信息管理系统，你需要知道这些

的最大值加1（以包含学号0），则可以直接以学号作为数组的索引值。由于学号是由6字节组成的，因此数组必须能够容纳2⁴⁸条记录，需要占用多少存储空间呢？就算一条记录只占用一个字节，也需要262144 G存储空间，何况电脑硬盘没这么大！如果只使用其中的10000条记录，则剩下的（2⁴⁸-10000）空间就会造成极大的浪费，显然这种方式是不可取的。

在查找算法中，非常经典高效的算法是"二分法查找"，按10000条记录算，最多也只需要比较14次（log₂¹⁰⁰⁰⁰）。但使用"二分法查找"的前提是信息必须有序排列，即要求学生记录必须按照学号的顺序存储，这就导致在添加或删除学生信息时，数据库存储的信息需要进行大量的移动操作。比如，数组中已经按照学号从小到大的顺序存储了9999条记录，现在写入第10000条记录，若该记录的学号最小，需要写入到所有记录的前面，这就需要将之前存储的9999条记录全部向后移动一次，以预留出首元素的空间，然后将新的学生记录写入首元素对应的空间中。由此可见，虽然使用这种方法可以提高查找效率，却牺牲了添加信息时的效率。

为了在添加信息时不进行大量的数据移动，能否换一种存储方式呢？比如，使用存储空间不连续的"单向链表"结构，将各个学生记录"链"起来，其示意图详见图3.23。

图3.23  使用单向链表管理学生记录

当使用链表管理学生记录时，实现有序排列只需每次插入新结点时，找到正确的插入位置，无需进行大量数据的移动。由于存储空间不连续，因此无法使用"二分法"查找学生信息，则实现有序排列也没有解决查找效率低下的问题，无论是否有序，查找时都需要从头开始顺序查找。

由此可见，使用"二分法查找"必须牺牲记录写入的效率以实现所有记录有序排列，使得写入记录的效率非常低。虽然基础的"顺序查找"对写入记录的效率完全不影响，但查找效率极为低下。因此，这两种情况都太极端了，要么选择极低的写入效率，要么选择极低的查找效率。何不将二者结合一下，以折中写入的效率和查找的效率呢？比如，将记录"二分"为两部分，使用两个数组来存储：

  student_t  student_db0[5000];

student_t  student_db1[5000]; 

假设规定，学号小于某值（即201044700239）时，记录存储在student_db0中，反之，记录存储在student_db1中。如此一来，在写入记录时，只需要多一条判断语句，对性能并没太大影响。而在查找时，只要根据学号判断记录在哪一个数组中，即可按照顺序查找的方式查找。此时，查找需要比较的次数就从最大的10000次降低到了5000次。由此可见，通过一个简单的方法，将信息分别存储在两个数组中，就可以明显地提高查找效率。为了继续提高查找的效率，还可以继续分组，比如，分成250组，每组的大小为40：

student_t  student_db0[40];

student_t  student_db1[40];

……

student_t  student_db248[40];

student_t  student_db249[40]; 

显然，采用这种定义方式太繁琐了，由于每个数组的大小是相同的，因此可以直接将存储40个学生记录的数组定义为一个类型：

  typedef student_t student_group_t[40];

student_group_t student_db[250];

此时，每个分组的大小为40，从而使得查找记录时，最多只需要比较40次。接下来，需要定义分组规则，以通过学号找到该记录属于哪个组。在定义规则时，应尽可能地使所有记录平均地分布在各个组中，不应该出现一些组存储的记录非常多，而一些组存储的记录非常少的情况。但这并不是一件容易的事情，需要对学号的数据分布进行精确的分析。

如果分成250组，假定学号是均匀分布的，则可以将6字节学号数求和除以250（分组数目）所得的余数（取余法）作为分组的索引，由于写入和查找时，都需要通过学号找到该记录应该属于哪个组，因此可以根据学号分组的依据，编写一个通过学号找到对应分组索引的函数，详见程序清单3.62。

程序清单3.62  通过学号分组范例程序

1    int db_id_to_idx(unsigned char id[6])

2    {

3        int i, sum = 0;

4

5        for (i = 0; i < 6; i++) {

6            sum += id[0];

7        }

8        return sum % 250; 9    }