传统意义上，图数据的存储结构有两类：相邻矩阵（Adjacency Matrix）和相邻链表（Adjacency List）。用相邻矩阵存储图数据的结果是会得到一个占用存储空间巨大但却相当稀疏的矩阵，这显然是一种非常低效的存储；相比而言，存储效率更高的相邻链表虽然在工业界中有着更广泛的应用（例如Facebook社交图谱的底层技术架构代码Tao/Dragon采用的就是相邻链表的方式），但在遇到热点（一个顶点有极其多的邻边）时会产生超长链表，因而造成访问延迟高、无法实现并发操作等。因此，设计并实现更高效的图存储、图计算数据结构和架构是Ultipa为整个数据库行业带来的最底层的创新与贡献。

图数据的存储结构必须同时满足以下几点：

• 高效的存储
• 低延迟的访问
• 对并发的支持

首先，为满足前面两点要求，Ultipa使用了C/C++中的动态向量数组设计并实现了相邻哈希（Adjacency Hash，Ultipa专利）结构，能够分别以O(1)、O(2)的延迟完成对图中任意顶点、边的定位。

针对传统哈希的单线程、单任务的特征，Ultipa借助下列技术手段将相邻哈希改造为单写-多读（single-writer-multiple-reader）甚至是支持多写多读的高并发工作方式：

• 版本号记录（Versioning）
• 读-拷贝-更新（RCU，Read-Copy-Update）
• 开放式寻址（Open-Addressing）

为了实现真正意义上的可扩展、高并发的哈希数据结构（多读-多写的哈希），Ultipa解决了两个主要问题：

• 无阻塞或无锁式设计（Non-blocking and Lock-Free）
• 精细颗粒度的访问控制（Fine-granularity Access Control）

由于此二者都和并发访问控制高度相关，对此Ultipa的工作重点是达到以下目标：

• 核心区域（访问控制）：
  • 区域足够小
  • 执行时间足够短
• 通用数据访问：
  • 避免不必要的访问（Unnecessary）
  • 避免无意识的访问（Unintentional）
• 并发控制：
  • 使用精细颗粒度的锁实现，例如lock-striping（条纹锁）
  • 采用推测式上锁机制，例如交易过程中的合并锁机制（Transactional Lock Elision）