(
课件网) 6.1 实时查询系统中数据的组织 实 时 查 询 大数据背景下，全部数据的组织、存储和处理，仅凭单个服务器和数据库 的数据组织与存储方式，无论从存储容量还是处理速度上都不能满足实际 应用的需求。 此时，采用分布式存储技术，将所有数据分别保存在不同的服务器中， 需要时从中提取并进行合并，就可以满足海量数据的存储与处理需求。 分布式存储系统利用分布在不同物理位置的服务器来分担系统存储任务， 既能提高数据存储的安全性，又能提升系统数据访问的速度，同时也具有 较好的可扩展性。当用户提出访问请求时，系统根据元数据服务器（进行 数据访问索引的服务器）将访问定位到目标数据的服务器上。 实时查询系统中的数据业务特点 1.能实现上千个请求的实时响应。网站应能做到 “即点即现”。 2.支持后续商品信息的更改。如删除、增加商品。 面对这种查询业务，为了减轻磁盘数据库访问的负 担，可事先将数据库中的商品信息读取出来并保存 在内存中，这样用户的查询就能直接面对内存进行， 大大提高数据读取的速度。 实时查询系统中的数据结构和算法设计 当数据从磁盘数据库读取出来并保存到内存中时，需要考虑用某种数据结构 来组织并存储。这种数据结构既能体现数据之间的逻辑关系，又能为后续的 查询提供算法上的支持。 数组 链表 队列 树 1.基于数据间线性关系的数据结构设计 （1）数组 数据从数据库中读取到数组后，可事先按照各个属性（如人气、销量、 信用、价格等）进行排序并分类存储，当用户发出相应的请求时，系统 就从已排序数组中选择符合用户查询要求的内容呈现给用户。 基于这种数据结构的问题主要出现在后续的商品信息维护阶段。当商家 增加了新品时，系统需要在数组中插入一个新数据并维持数组元素继续 有序。 查找：即在一个有序序列中查找新增元素的插入位置，可以采用二分查找 算法，时间复杂度为O()(n表示数组元素的总个数)，速度比较快。 插入：即在找到可以插入的位置x后，将新元素插入到找到的位置x中，但 必须先将位置x到n之间的所有元素往后移一位，为新元素空出位置，这个 时间复杂度就比较大，为O(n)。当瞬间有上千名用户提出请求，同时进行 上千个这样的处理时，时效性较差。 （2）链表 针对在数组中插入新元素时引起的数据移动低效的问题，可以考虑用链表 代替数组。因为在一个链表中插入一个新元素，时间复杂度为O(1),大大优 于采用数组时O(n)的线性复杂度。 插入操作主要涉及查找和插入两个关键操作，链表虽然在插入操作时能确保 O(1)的时间复杂度，但在进行查找时（查找新元素的插入位置），却需要从 链表的一端依次遍历查找，时间复杂度为O(n)。因此，采用链表来存储数据， 虽然整体复杂度有所下降，但O(n)的复杂度还是达不到现实的需求。 2.基于链表的数据结构和算法优化设计 基于链表的处理，只是在查找时效率较低，而插入操作却完全能满足要求，所以可以在链表的基础上继续加以改进，以解决顺序查找导致的低效问题。主要考虑从查找角度来优化数据结构，这个改进可按以下思路进行。 （1）减少查找插入位置过程中的比较次数 基于链表数据结构的处理时间主要消耗在插入位置的查找中，因此，可着眼减少查找过程中的数据两两比较的次数来优化数据结构。 （2）借鉴二分查找算法的思想 二分查找算法之所以效率较高，首先是因为数据是有序的，其次是利用 有序性进行跨区间、跳跃性的比较，从而避免低效的逐个依次比较。 实现的思路是首先将数据进行有序化处理，然后想二分查找一样确定比较 的关键节点，根据新元素与关键节点的比较结果来高效地取舍剩余的查找 区间。 1 3 4 10 13 15 20 原链表 1 4 10 15 关键节点 在原链表 ... ...
