内存数据库技术及其应用研究(5)
引数据全在内存中，所以指针在数据结构中被广泛的使用。[9]
应用进程可以通过
指针或者位置独立的数据库偏移量来访问数据， 无需像磁盘数据库系统那样通过
缓冲区访问磁盘数据。其次，若一个大的数据对象在数据库中多次出现，则内存
中只需存储一次，其它地方使用指针来引用。
2.2.2 索引结构
传统的磁盘数据库系统的索引结构主要是 B/B+树，其设计的目的主要是以
改善cache 性能为出发点，减少磁盘的I/O次数，以较少的磁盘存取为代价来访
问数据。而在内存数据库系统中，数据结构设计的目的主要是减少内存的开销和
处理器需要执行的指令数，所以需要采用不同的索引结构。目前，人们已提出了
多种索引结构，其中比较流行的是hash 索引T 树索引结构（T-Tree） 。
T 树索引是由AVL 树和B树发展而来的，其节点的数据结构如图所示： 可以看出，由于是二叉树，所以T 树具有AVL树的高效的二分查找特性，但
同时由于高度一般高于B树，所以在对数据读写时加锁的开销更大。因为一个节点可以包含多个元素，所以和B树一样，T 树也具有良好的更新和存储特性。与
磁盘索引结构的B树不同，它不一定要求路径最短，这主要是因为内存的树的遍
历速度要远高于磁盘。因为每个节点都保持在半满河全满之间，所以索引一般不
需要溢出块，由插入和删除所引起的数据移动通常只需要在一个节点内进行，减
少了为了保持树平衡所需要的旋转操作。[10]
由于索引和数据全都保存在内存中，
所以在一个T 树节点中不需要像B树那样存放索引键值—指针对， 只需要存放指
向内存中相应记录对应字段的指针即可。而且，元组和数据可以分开存储，元组
仅保存指向数据的指针，数据可以散布于内存中。这样，索引中变长字段的存储
不再是问题。此外，因为指针一般比它指向的字段要小，所以可以节省大量的内
存空间。因此目前主流的内存数据库均采用T 树作为通用的索引结构。
2.2.3 并发控制
并发控制的开销对数据库系统性能的影响很大， 传统的磁盘数据库系统通常
都采用细粒度的锁控制， 以保证事务的并发。 然而内存数据库的常驻内存的特性，
使其与传统的数据库系统有所不同：首先，内存访问速度要比磁盘快得多，因此
在内存数据库系统中，同样一个事务的执行时间会比磁盘数据库要短的多，所以
在基于锁的并发控制系统中，锁的时间将会很短，对锁的竞争比磁盘数据库小。
其次，磁盘数据库系统一般把锁保存在内存中，数据保存在磁盘中，而内存数据
库系统将数据、元数据均常驻内存，使得系统可以采用统一的方式访问它们。
在实际的应用中， 内存数据库使用的并发控制机制与磁盘数据库的基本相同，
但在细节上存在一定差异。由于全部数据都存储在内存中，事务执行时间较短，
持有锁的时间也较短，所以系统中并发冲突较少，因此主要可以通过以下方法减
少锁的开销：
（1）采用较大的锁粒度（如表级锁、库级锁）；
（2）采用乐观加锁方式；
（3）减少锁的类型；
（4）将锁信息存储在数据本身。
一般的磁盘数据库系统采用的是细粒度锁（字段、记录） ，可以减少竞争，
提高并发度，但是锁的开销会增大；采用粗粒度锁（关系，甚至整个数据库）情
上一篇：WEB服务器的设计与实现