数据库得查询功能是怎么实现的

　　数据库的查询功能实现原理：

　　数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找（linear search），这种复杂度为O(n)的算法在数据量很大时显然是糟糕的，好在计算机科学的发展提供了很多更优秀的查找算法，例如二分查找（binary search）、二叉树查找（binary tree search）等。如果稍微分析一下会发现，每种查找算法都只能应用于特定的数据结构之上，例如二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上，但是数据本身的组织结构不可能完全满足各种数据结构（例如，理论上不可能同时将两列都按顺序进行组织），所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。

图1展示了一种可能的索引方式。左边是数据表，一共有两列七条记录，最左边的是数据记录的物理地址（注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的）。为了加快Col2的查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针，这样就可以运用二叉查找在O(log2n)O(log2n)的复杂度内获取到相应数据。

移动计算是随着移动通信、互联网、数据库、分布式计算等技术的发展而兴起的新技术。移动计算技术将使计算机或其他信息智能终端设备，在无线环境下实现数据传输及资源共享。它的作用是，与中央信息系统相互作用，分担中央信息系统的计算压力，将有用、准确、及时的信息提供给任何时间、任何地点的任何客户。移动计算环境比传统的
　　计算环境更为复杂和灵活，具有移动性、低带宽、频繁断接性、网络通信的非对称性、电源能力的有限性等特点，这使得传统分布式数据库中的方法和技术不能直接应用于移动数据库。
　　根据嵌入式移动数据库自身所具有的特点，采用与普通数据库不同或更优的查询策略变得尤为重要。本文介绍了位置相关查询优化和数据广播两种普遍用于移动数据库查询的方法，结合移动数据库中的缓存技术，分别从合理分配嵌入式移动数据库资源和在一定程度上解决移动数据库的断接问题这两点，实现嵌入式移动数据库的查询优化。
　　1 位置相关查询优化
　　1.1 嵌入式移动数据库的结构体系及特点
　　在传统的分布式计算系统中，各个计算节点之间是通过固定网络连接并保持网络的持续连接性的，而移动计算系统改变了这种假设条件。移动计算系统是固定节点和移动节点构成的分布计算系统。
　　移动计算的网络环境具有自身的特点：移动性、断接性、带宽多样性、可伸缩性、弱可靠性、网络通信的非对称性、电源能力的局限性等。
　　移动数据库的计算环境是传统分布式数据库的扩展，可以看作客户端与固定服务器节点动态连接的分布式系统，因此移动计算环境中的数据库管理系统是一种动态分布式数据库管理系统。