数据挖掘是在海量的数据中提取隐含的、未知的、潜在有用的知识或信息模式的决策支持方法，是20世纪90年代初针对“数据丰富、知识贫乏”问题应运而生的一种新技术。为了有效地从海量数据中提取信息，数据挖掘算法必须具有良好的可伸缩性，也就是说，数据挖掘算法的运行时间必须是可预计的、可接受的。 在众多方法中，基于空间划分的方法是一种有效处理海量数据的数据挖掘方法，其主要应用于聚类分析算法与孤立点检测算法。然而，现有的基于空间划分的方法却存在如下问题：第一，由于空间划分时产生的单元数与维数呈指数增长，该方法多适用于维数相对较低的数据。第二，在一些基于空间划分的数据挖掘方法中，如基于单元的聚类算法，如果划分粒度越细，则聚类精度越高，但同时粒度越细生成的单元数也越多，造成算法效率下降。如果划分的粒度变粗，则算法精度难以保证。 针对目前基于空间划分的方法存在的问题，本文提出了一种新的基于空间划分的索引结构CD-Tree。为了降低空间复杂度，在保持单元间关系的条件下，CD-Tree只保存了非空单元，使得聚类与孤立点检测过程易于实现。文中给出了CD-Tree详细定义，设计了CD-Tree的构建、节点删除、树合并等相关算法，分析了CD-Tree相关算法的时间复杂度，并与其它存储结构的时间复杂度进行了对比。通过理论分析，对于空间划分问题，CD-Tree结构要优于其它可用于存储划分后单元的结构。 CD-Tree适用于当空间划分产生较多的空单元情况，而空单元的数量与数据的偏斜程度有关，数据偏斜程度越高，则生成的空单元数越多。为了确定CD-Tree的适用条件，需要一个度量来衡量空间划分下的数据偏斜程度。现有的衡量数据偏斜的度量不能用于衡量空间划分下的数据偏斜程度，本文提出了一种新的偏斜度的度量DSF(Data Skew Factor)。DSF相当于划分后空单元所占的比例，可用来估计生成非空单元数目。另外，DSF还可用于优化CD-Tree结构及在数据流聚类中动态调整划分的粒度。 在CD-Tree及DSF基础上，本文研究了基于空间划分的优化聚类算法及相关技术，具体包括：基于空间划分的聚类算法；基于空间划分的数据流聚类算法；基于空间划分的孤立点检测算法。 在基于空间划分的聚类算法方面，分析现有的基于空间划分的聚类方法的特