B+树阶数m的最优选取

本文指出对普通的B^ 树作了一定的限制后，当选择B^ 树适当的阶数m时，对B^ 树索引文件的时间和空间利用率有一个最优的设计过程，分别给出了应用在两种数据库系统模型中的B^ 树索引文件结构：（1）具有有限内存的数据库系统（Database Systems with Limited Amount of Main Memory,简称为DBSLAM），在DBSLAM模型中，我们只是缓存B^ 树中的部分结点；（2）具有极大内存的数据库系统（Database Systems with Very Large Amount of Main Memory，简称为DBSVLAM）,在DBSVLAM模型中，我们将缓存B^ 树中所有的结点，基于以上两种模型，我们分别建立了两个不同的时空开销模型，并以此进行了优化设计。     

B^＋树它引文件结构的优化设计

指出当普通Ｂ＾＋树的数据块设计为定长时,数据块长度的选择具有一个最优的选取设计过程。给出了在两种数据库系统模型中,对Ｂ＾＋树索引文件结构的优化设计：⑴在具有限量内存在数据库系统ＤＢＳＬＡＭ（Ｄａｔａｂａｓｅ Ｓｙｓｔｅｍｓ ｗｉｔｈ Ｌｉｍｉｔｅｓｄ Ａｍｏｕｎｔ ｏｆ Ｍａｉｎ Ｍｅｍｏｒｙ）模型中,只有缓存Ｂ＾＋树中的部分结点;⑵具有极大数量内存在的数据库系统ＤＢＳＶＬＡＭ（Ｄａｔａｂａｓｅ     

改进型缓存敏感B+树的研究

在内存数据库中,处理器缓存的失配次数对系统的性能有重要的影响;缓存敏感的索引能减少在做查询操作时产生的缓存失配次数,从而提高系统的性能;传统的设计思路将结点大小等于缓存块大小,认为这样就能使得缓存失配次数减少;但是这样的设计忽略了TLB失配对系统性能的影响;我们提出了一种缓存敏感索引——改进型缓存敏感B＋树（简称MCSB＋树）,它同时兼顾了缓存失配和TLB失配对系统性能的影响。比传统的缓存敏感索引能提供更好的操作性能。     

IP交换机中嵌入式内存数据库HSQL的索引优化

该文分析总结了当前在内存数据库中提高树索引的缓存敏感性的主要技术,设计并实现了一个具有缓存敏感性的AVL树,即CC-AVL树。CC-AVL树合理利用缓存行的大小,并构造父子节点在内存中连续存储的结构,从而使一个缓存行中包含正要访问的节点和其左孩子节点,同时使用CPU支持的数据预取技术获得右孩子节点。从而使CC-AVL树比AVL树具有更高的缓存敏感性。CC-AVL树被用于一个运行在IP交换机中的嵌入式内存数据库HSQL中。     

HT树：缓存敏感的内存数据库索引

在内存数据库系统中,针对处理器缓存对提高内存数据库的性能有重要影响的情况,在B＋树的基础上提出一种新的缓存敏感的索引——HT索引。将Hash方法和树结构相结合,构造一种适用于内存数据库的索引。结果证明,该索引结构能提高处理器缓存的利用率,其整体操作性能优于传统的缓存敏感索引。     

基于混合内存的Apache Spark缓存系统实现与优化

随着大数据时代数据规模的激增,内存计算框架得到了长足发展。主流内存计算框架Apache Spark使用内存来缓存中间结果,大幅度地提升了数据处理速度。同时,具有较快的读写速度和较大容量的非易失性存储器NVM在内存计算领域展现出了巨大的发展前景,使用DRAM和NVM构建Spark混合缓存系统成为一种可行方案。文中提出了一种基于DRAM-NVM混合内存的Spark缓存系统,该系统选择平面混合缓存模型作为设计方案,然后为缓存块管理系统设计了专用的数据结构,并提出了适用于Spark的混合缓存系统整体设计架构。另外,为了将频繁访问的缓存块保存在DRAM缓存中,提出了基于缓存块最小重用代价的混合缓存管理策略。首先从DAG信息中获取RDD的未来重用次数,未来重用次数多的缓存块将被优先保存在DRAM缓存中,并在缓存块迁移时考虑了迁移成本。设计实验表明,DRAM-NVM混合缓存相比原有缓存系统的性能平均提升了53.06%,对于相同的混合内存,所提策略相比默认缓存策略有平均35.09%的提升。同时,使用文中设计的混合系统只需要1/4的DRAM和3/4的NVM作为缓存,就能达到全部DRAM缓存约79%的性能...     

内存数据库系统SwiftMMDB索引机制的设计与实现

T树结合了平衡二叉树(AVL树)和B树的优点,可以有效地组织索引数据,从而为内存数据库提供优良的存储效率和查询性能。结合自主开发的一个内存数据库系统SwiftMMDB介绍T树索引的设计与实现,并通过节点分裂、填充等方法改进了经典T树的插入和删除操作,减少了T树中平衡旋转的次数,从而进一步提高内存数据库检索的效率和性能。     

DCST:主存空间高效的缓存敏感型T-树索引研究

已有主存索引通过指针消除和预取机制提升索引结构的缓存感知能力,减少缓存失效次数,但是并没有有效地利用现代计算机的CPU性能和内存空间。为了进一步提升索引结构对内存空间以及CPU性能的利用率,提出了DCST-树索引结构。该索引结构采用数据压缩的方式,对结点中的关键字进行压缩,提高索引结构对内存空间和缓存空间的利用率,减少内存访问次数,提高缓存命中率。同时,对结点进行分区,增加结点容量,提高结点扇出度,降低树的高度。实验结果表明,所提方案比现有主存索引机制具有更加高效的空间利用率和缓存感知能力,同时具有更加优秀的查询处理能力。     

基于图划分抽样算法的图表示学习

在基于神经网络的图表示算法中,当节点属性维度过高、图的规模过大时,从内存到显存的数据传输会成为训练性能的瓶颈。针对这类问题,该方法将图划分算法应用于图表示学习中,降低了内存访问的I/O开销。该方法根据图节点的度数,将图划分成若干个块,使用显存缓存池存储若干个特征矩阵块。每一轮训练,使用缓存池中的特征矩阵块,以此来减少内存到显存的数据拷贝。针对这一思想,该方法使用基于图划分的抽样算法,设计显存的缓存池来降低内存的访问,运用多级负采样算法,降低训练中负样本采样的时间复杂度。在多个数据集上,与现有方法对比发现,该方法的下游机器学习准确率与原算法基本一致,训练效率可以提高2~ 7倍。实验结果表明,基于图划分的图表示学习能高效训练模型,同时保证节点表示向量的测试效果。今后的课题可以使用严谨的理论证明,阐明图划分模型与原模型的理论误差。     

B+树索引机制的研究及优化

B+树索引是大型数据库系统中较为常用的一种索引技术。当数据庞杂时,B+树索引在查找效率和空间利用率方面还存在不足。针对该问题提出一种改进的B+树结构,首先通过调整叶子结点与非叶子结点的数量关系,以降低树的深度;然后优化原插入算法,在分裂结点前进行平衡处理(BP),以提高树的空间利用率。经试验,改进后的B+树与传统B+树相比,在查找效率和空间利用率上分别提高了10%和6%,证明对B+树的改进具有可行性。     

基于视频块的结构化时移流查询模型

针对基于结构化P2P的时移流系统的维护开销较大、扩展性较差等问题,提出一个基于视频块的结构化时移流查询模型。根据节点缓存的首视频块进行分层,通过节点注册缓存中所有视频块的方法,降低层节点需要维护的路由信息,解决系统中缓存视频块不能完全找到的问题。实验结果表明,该模型具有较高的缓存命中率、较好的查询性能和较低的维护开销。     

支持高并发数据流处理的MapReduce中间结果缓存

针对面向大规模历史数据的高并发数据流处理需求,为改进MapReduce的实时处理能力,提出了一种内存Hash B树、外存SSTable文件的key/value中间结果缓存,该结构具有可划分性、可扩展性和高效性.在此基础上,利用B树的平衡性特征提出了一种基于概率的B树构造算法和多路查询算法,利用读写开销估算和缓冲区信息改造了外存文件读写策略和内外存替换算法,进一步优化了中间结果的高并发读写性能.算法分析和实验证明了该缓存的有效性.     

NUMA感知的持久内存存储引擎优化设计

持久性内存(persistmemory,PM)具有非易失、字节寻址、低时延和大容量等特性,打破了传统内外存之间的界限,对现有软件体系结构带来颠覆性影响.但是,当前PM硬件还存在着磨损不均衡、读写不对称等问题,特别是当跨NUMA(nonuniformmemoryaccess)节点访问PM时,存在着严重的I/O性能衰减问题.提出了一种NUMA感知的PM存储引擎优化设计,并应用到中兴新一代数据库系统GoldenX中,显著降低了数据库系统跨NUMA节点访问持久内存的开销.主要创新点包括:提出了一种DRAM+PM混合内存架构下跨NUMA节点的数据空间分布策略和分布式存取模型,实现了PM数据空间的高效使用;针对跨NUMA访问PM的高开销问题,提出了I/O代理例程访问方法,将跨NUMA访问PM开销转化为一次远程DRAM内存拷贝和本地访问PM的开销,设计了Cache Line Area (CLA)缓存页机制,缓解了I/O写放大问题,提升了本地访问PM的效率;扩展了传统表空间概念,让每个表空间既拥有独立的表数据存储,也拥有专门的WAL (write-ahead logging)日志存储,针对该分布式WA...     

基于B+树存储的AABB包围盒碰撞检测算法

对于碰撞检测算法,使用传统的AABB包围盒来构建包围盒层次树时,其包围盒层次树的层数、叶子结点的个数和各结点的存储字节数是影响碰撞检测效率的主要因素.为了减少结点存储容量对碰撞检测效率的影响,提高碰撞检测的效率,文中采取B+树的存储结构来存储包围盒等信息.在包围盒相交测试之前,使得各结点存储索引有序,不需要再对各结点进行额外的排序,减少了内存开销,并且避免了不必要的包围盒测试.此外B+树的非叶子结点不存储具体的数据信息,从而减少了整棵树的存储空间.实验表明,在检测环境和检测对象相同的条件下,使用B+树存储的AABB包围盒碰撞检测算法的检测时间明显比传统的AABB算法短.     

Spark中一种高效RDD自主缓存替换策略研究

由于并行计算框架Spark缓存替换算法的粗糙性,LRU（least recently used）算法并未考虑RDD的重复使用导致易把高重用数据块替换出内存且作业执行效率较低等问题。通过优化权重模型和改进替换策略,提出了一种高效RDD自主缓存替换策略（efficient RDD automatic cache,ERAC）,包括高重用自主缓存算法和缓存替换分级算法,可实现高效RDD的自主缓存和缓存目标的分级替换。最后利用SNAP（Stanford network analysis project）提供的标准数据集将ERAC和LRU、RA（register allocation）等算法进行了对比实验,结果显示ERAC算法能够有效提高Spark的内存利用率和任务执行效率。     

航天实时内存数据库存取机制MCacheTree的研究

考虑到空间环境探测、空间科学实验所产生的数据时效性比较强,为了对它们进行有效的管理,研究了提高实时性能的索引技术.由于IO速度较慢、外存延迟时间难以预测,实时数据库系统通常采取内存数据库技术.基于此,提出了一种新的适合航天实时内存数据库系统的索引结构:MCacheTree,它将内存缓存和检索树有机地结合起来,并应用延迟写和延迟删除的优化技术,有效地降低了查询时间,提高了实时性能.最后通过实验验证了该设计的高效性.     

广域传感器数据库中的缓存技术研究

广域传感器数据库是当前国际上备受关注的由多学科高度交叉的新兴热点研究领域。广域传感器数据库具有巨大的应用价值,应用前景十分广阔。基于缓存技术和预取技术,提出了一种缓存技术与预取技术相结合的体系结构。对体系结构中各个模块的功能和实现算法进行了详细阐述,对算法进行了复杂性和实例分析,有效地解决了广域传感器数据库系统中,低频结点数据进入缓存替换出高频结点数据所造成的缓存命中率低和系统资源浪费问题。     

基于父结点的信息预报马尔可夫模型

节点扰动（churn）是制约P2P系统性能的重要原因,当移动结点（用户）进入P2P网络中（点播或直播）观看节目时,其它节点对其进行数据块传送具有不确定性。本文在以前建立移动结点信息预报的马尔可夫模型基础上,基于父结点建立信息预报马尔可夫模型,从另一个角度对父结点传信息给移动结点的概率进行评估,最后用理论和实验证明了父结点信息传送的概率稳定度。     

新一代高端服务器的标准──康柏8路处理器系统结构

（接上期）●缓存加速器为了保持在三条总线上的数据的一致性,康柏８路ＳＭＰ系统应用缓存加速器来减少处理器总线上不必要的阻塞。一个具有挑战性的ＳＭＰ设计是使所有处理器和Ｉ／Ｏ子程序来保持内存的一致性,这是一个典型保持数据一致性的方式。由于数据是被处理器总线上的多个缓存器和主内存共享,这里存在着相同的地址而数据却不一致的可能性。Ｉｎｔｅｌ处理器支持一个探测的协议来解决缓存一致性的问题,在一个典型的双总线的设计中,一个处理器总线上的内存事务处理是探测远程总线以确保最新数据被使用,每一个探测循环消耗带宽并…     

HOFT密钥管理方案约束优化研究

在特定的密钥更新通信开销的情况下,研究了基于混合单向函数树的高效安全组播密钥管理方案问题。混合单向函数树方案将含N个成员的组划分为若干个含M个成员的簇,并将每个簇安置在密钥管理树的叶子结点上。根据簇大小,将组控制器的密钥最小存储开销表达为约束优化问题,再将约束优化问题转化为一个关于簇大小M的不动点方程,当密钥更新通信开销约束为O（logN）时,证明不动点方程的最大根为簇大小的最优值,它使得混合树的最小密钥存储开销为O（N/logN）。同时设计了一种构造具有最小存储开销的混合单向函数树的算法。