- 积分
- 19528
- 明经币
- 个
- 注册时间
- 2015-8-18
- 在线时间
- 小时
- 威望
-
- 金钱
- 个
- 贡献
-
- 激情
-
|
本帖最后由 你有种再说一遍 于 2025-7-27 00:59 编辑
# Z-order曲线
我在想:如果重新设计CAD,那么有什么现代技术是可以用上的?
CAD数据库场景要求
1,用户交互必然是很慢的,表示我们插入速度可以慢.
毕竟没有人可以一秒钟画1K图元.
2,查询速度必然需要快,尤其是能够实现:
多核并行+SIMD+AoSoA列式储存 => 高速的现代化查询和修改.
数落一下现有结构的一些缺点:
四叉树八叉树(排除B+树)
并行效率并不好,是所有树形结构本身的缺陷.
例如我要全部图元平移一个向量进行修改,此时树形结构的成本巨大,
除了节点锁控制,索引层要全部重建,因此索引层要变薄才行.
更何况它们难以mmap模式序列化(定长分块映射到硬盘,没改的就不写入)
哈希网格可以有高效的并行,但是它扩容和初始化存在问题.
扩容前用一致性哈希进行预先分块?这太麻烦了.
有什么技术是既可以排序分块用上并行查询和修改,又可以扩容简单呢?
有的,兄弟有的.
Z-order曲线排序就是这样的功能,又叫Morton莫顿码.
这个技术真是继约束求解器另一重大发明.
## 原理
数据库的列X和列Y.(想象成Excel的两列int就好了)
列X有序,列Y是无序的.就跟点集一样.
| X (有序) | Y (无序) | 其他列..
|---------|---------|----|
| 1 | 23 |
| 102 | 5 |
| 301 | 17 |
| 304 | 2 |
| 405 | 31 |
| 600 | 11 |
| 711 | 7 |
1,列X可以二分等操作进行检索,也就是自带索引.索引的目的就是跳过无用的比较.
2,联合查询X和Y,会进行索引覆盖,毕竟X是有序的,先X再Y享受到前者的索引,这个就是最左前缀原则.
3,但是单独查询列Y呢?例如:检索 Y=150是否存在.
那么就需要遍历全部.
遍历是每个程序员都需要拒绝的行为!!
应该没有傻瓜想着把Y排序构造索引,再回表到X吧.
因此我们用Z-order排序,它只是返回一个码,是一种排序规则.
`ptList.OrderBy(pt => ZOrder(pt));`
```csharp
using System;
using System.Runtime.Intrinsics.X86;
class Program
{
// 传统方法（用于对比）
static ulong ZOrderLegacy(int x, int y)
{
ulong z = 0;
for (int i = 0; i < 32; i++)
{
z |= ((ulong)(x >> i) & 1) << (2 * i);
z |= ((ulong)(y >> i) & 1) << (2 * i + 1);
}
return z;
}
// 使用 BMI2 指令集的优化方法（需要支持 AVX2 的 CPU）
static ulong ZOrderBmi2(int x, int y)
{
if (Bmi2.X64.IsSupported)
{
// 使用 PDEP 指令（Parallel Bits Deposit）高效交错位
ulong x64 = (uint)x; // 零扩展为 64 位
ulong y64 = (uint)y;
// 掩码：0x5555555555555555（0101...01）
const ulong mask = 0x5555555555555555UL;
// 将 x 的位放入偶数位（0,2,4,...）
ulong xPart = Bmi2.X64.ParallelBitDeposit(x64, mask);
// 将 y 的位放入奇数位（1,3,5,...）
ulong yPart = Bmi2.X64.ParallelBitDeposit(y64, mask << 1);
return xPart | yPart;
}
else
{
throw new("不支持SIMD的Z-Order指令,你可以选择回退到传统");
}
}
static void Main()
{
int x = 13;
int y = 10;
Console.WriteLine($"x = {x} (二进制: {Convert.ToString(x, 2).PadLeft(4, '0')})");
Console.WriteLine($"y = {y} (二进制: {Convert.ToString(y, 2).PadLeft(4, '0')})");
// 传统方法
ulong zLegacy = ZOrderLegacy(x, y);
Console.WriteLine($"\n传统方法结果:");
Console.WriteLine($"Z-order值: {zLegacy}");
Console.WriteLine($"二进制: {Convert.ToString((long)zLegacy, 2).PadLeft(8, '0')}");
// SIMD 优化方法
ulong zBmi2 = ZOrderBmi2(x, y);
Console.WriteLine($"\nBMI2 优化方法结果:");
Console.WriteLine($"Z-order值: {zBmi2}");
Console.WriteLine($"二进制: {Convert.ToString((long)zBmi2, 2).PadLeft(8, '0')}");
// 验证结果是否一致
Console.WriteLine($"\n结果一致: {zLegacy == zBmi2}");
}
}
```
```
x = 13 → 二进制位: [x3=1][x2=1][x1=0][x0=1]
y = 10 → 二进制位: [y3=1][y2=0][y1=1][y0=0]
实际计算过程从低位到高位:
x的位: x0=1, x1=0, x2=1, x3=1
y的位: y0=0, y1=1, y2=0, y3=1
交错顺序（从最低位开始）:
位位置: 7 6 5 4 3 2 1 0
对应位: y3 x3 y2 x2 y1 x1 y0 x0
填充后: 1 1 0 1 1 0 0 1
最终值: 0b11011001 (217)
```
它的算法叫做保序映射,就只是交错bit:
...[y3][x3][y2][x2][y1][x1][y0][x0] <-这边开始,也就是X再Y(大部分)
...[x3][y3][x2][y2][x1][y1][x0][y0] <-这边开始,也就是Y再X
二者其实没有什么本质区别,只是方向敏感性.
为什么保序映射可以做到?
它就像是两个向量的加法,两个向量变一个.融合两个值保留了空间性.
因为相近的两个点,交错之后数据是差不多的,只有末尾是不同,就自然可以用于排序了.
虽然有些地方的空间点是跳跃的,但是Z码距离是相近的,
它是不保证原有X顺序,是做到局部空间有序.
核心只有一句话: 多维映射成一维了!!
排序之后,定长切割,成为一个个区块.
我们仍然需要把每个区块里面X列和Y列遍历一次,
提取范围元数据Xmin Xmax Ymin Ymax写入分块中.
在CAD上面有个很好的比喻,就是做了一个数据层的包围盒.
这样查询就可以快速跳过不吻合区块,而不是进入区块内遍历全部行.
假阳性:
通过范围夹选多个区块,通过元数据过滤范围,再进行遍历行数据.
也就是区块夹选之后也是"弱遍历",为了进一步降低这成本,
还可以把范围的min做多一层索引,用有序容器排列一下它们.
不过我就偷懒不做了,这种查询成本太小,插入成本增加了,
或者我们可以在内存层做而不是储存层做,妙啊.
当我第一次看到这个的时候大受震撼,居然可以无视了Mysql的最左前缀原则.
用先计算并记录,来让查询变得简单高效,
是一种组成联合索引的方式,并且末尾丢失精度不需要关心,
也就是大约邻近分块就好了,始终查询的是元数据.
这个方式还是分析型数据库CK,Delta Lake的基础.
实际上排序再分块只是一个概念,
数据是插入的,插入时求这个Z码,然后二分到插入位置.
我们底层本质是List<区块>是有序的,这个"序"是Z-Order(Z码).
正所谓编程没有银弹,它的坏处也是有的:
使用Z-Order顺序后,无论以X作为查询条件还是以Y作为查询条件,都只能跳过50%的数据.
但是在满足查询满足最左原则的情况下,
由于Z-Order将原本自然顺序下有序的数据变得无序了,
因此反而降低了满足最左原则下的查询效率.
这种现象在小数据的情况下不明显,但是当数据量增加时,这种现象带来的影响会越来越大.
(摘录 https://zhuanlan.zhihu.com/p/491256487)
也就是它查询速度总是不那么好也不那么坏,但是和我们CAD有啥关系,我们更多是批量改.
## 一些性质
Z码有个性质,可以找到完全相同的Z码,来进行是否消重处理.
只是我们通常末尾会丢精度,就只是用于快速定位.
Z码编织可以织入时间和空间.
Z码它有一个问题,无法应对负数.
负数在计算机上面是补码形式,
int转为ulong就是一个极大值!!
并且我们不能把`负数*2-1映射到奇数,正数*2映射到偶数`
这种操作破坏了空间局部性,切割分块时候就出错了.
因此我们有三种选择,
一种:
是resize也就是每次都归一化.
记录min,当插入时候发现小于min,就开始全部数据重新偏移.
resize不好,毕竟你可能已经录入n多行的数据了.
二种:
遇到负数坐标,要建立四个象限.
其中2/3/4象限都是剥夺了符号的绝对值,各自储存,映射到了1象限,然后取出来的时候 还它 正负符号.
然后在Z码的ulong前两个bit划分成四个象限,就只有一个List储存辣.
三种:
Hilbert曲线(Z-order 的变种)支持带符号整数,
通过 Gray 码 将负数映射到正区间,同时保持局部性.
不过它引入了翻转操作,存在分支预测,修改和检索效率不如Z码
| 十进制 | 二进制 | Gray码 |
|-------|-------|-------|
| -8 | 1000 | 1100 |
| -7 | 1001 | 1101 |
| -6 | 1010 | 1111 |
| -5 | 1011 | 1110 |
| -4 | 1100 | 1010 |
| -3 | 1101 | 1011 |
| -2 | 1110 | 1001 |
| -1 | 1111 | 1000 |
| 0 | 0000 | 0000 |
| 1 | 0001 | 0001 |
| 2 | 0010 | 0011 |
| 3 | 0011 | 0010 |
| 4 | 0100 | 0110 |
| 5 | 0101 | 0111 |
| 6 | 0110 | 0101 |
| 7 | 0111 | 0100 |
## 隐含意义
数据库优化查询,只需要用莫顿码的`线性四叉树`这是另一个话题,我们跳过它.
图形学上面的运用不止上面那么简单.
Z-order真正的核心并不是上面的联合索引.
而是...它是一个隐含的模糊多叉树!!用于渲染.
我们现在有四个象限的Z码,相当于四个根节点,
也就是Z码的前两个bit表示象限,后面盖0.
那么再多两个bit显示呢?就可以看作是四叉树的层节点.
每下一层就再多2个bit,就越来越清晰,过滤程度就越高.
它是一个LOD的基操,
视角如果没看见的东西,储存的内容就根本不会加载进来,
太远了也只模糊显示,而不是全部.
这个和游戏设计理念是相符的,但是和CAD全图显示是不符的.
但是也可以采用LRU等算法优化这些显示,只是这个操作也属于底层实现.
如果大家没懂我这个说法,可以想象成卫星地图,
虽然卫星地图是GeoHash,也是一种曲线填充算法.
## 储存层
每个区块内容:
区块大小是限定的,通常是考虑为磁盘对齐.
每个数据字段都是Vector128,256之类,至于有几个字段就可以自己定义了,
可以先不考虑压缩,毕竟压缩就是破坏mmap,可以保留一种中间格式...
### 传统格式(废弃):
```
// 一级索引: 物理上按ID排序,类似数据库的聚簇索引
List<Entity> primaryTable = new () {
new Entity { Id = 101, Type = "Circle", X1 = 10, Y1 = 20, X2 = 30, Y2 = 40 },
new Entity { Id = 102, Type = "Rect", X1 = 15, Y1 = 25, X2 = 35, Y2 = 45 },
new Entity { Id = 103, Type = "Circle", X1 = 50, Y1 = 60, X2 = 70, Y2 = 80 }
// ...
};
// 二级索引: Z-order索引,按zvalue排序,需要回表
List<ZIndexEntry> zindex = new () {
new ZIndexEntry { ZValue = 0x1234, Id = 101 },
new ZIndexEntry { ZValue = 0x5678, Id = 102 },
new ZIndexEntry { ZValue = 0x9ABC, Id = 103 }
// ...
};
```
### 现代化格式(推荐):
(不过这还是行式储存,不太符合我要求,仅做示意)
```
// 一级索引: z-order值 → CAD实体
// Key: uint - z-order编码值
// Value: Entity - 对应的CAD图形对象
private readonly SortedDictionary<uint, Entity> _zOrderMap = new() {
{ 0x1234, new Entity { Id = 101, Type = "Circle", X1 = 10, Y1 = 20, X2 = 30, Y2 = 40 } },
{ 0x5678, new Entity { Id = 102, Type = "Rect", X1 = 15, Y1 = 25, X2 = 35, Y2 = 45 } },
{ 0x9ABC, new Entity { Id = 103, Type = "Circle", X1 = 50, Y1 = 60, X2 = 70, Y2 = 80 } }
// ...
};
// 二级索引:ID映射表：CAD对象ID → z-order值
// Key: int - CAD数据库中的对象唯一标识
// Value: uint - 该对象对应的z-order编码值
private readonly Dictionary<int, uint> _idToZIndex = new() {
{ 101, 0x1234 },
{ 102, 0x5678 },
{ 103, 0x9ABC }
// ...
};
```
```
// 按类型分表存储 + 同类数据AoSoA组织
struct CADDatabase {
AoSoA_Points points; // 点云数据
AoSoA_Lines lines; // 线段数据
AoSoA_Triangles tris; // 三角面
AoSoA_NURBS nurbs; // 曲面数据
// ...其他图元类型
SpatialIndex index; // 包含所有图元的空间索引
};
```
## 任务操作池
我对于目前数据库无法并行查询和修改很不满.
因为现代的需求已经进化到储存一亿个图元了.
我希望的是一次开发可以提供一组API对数据进行批量的列式修改,
而不是二开需要多线程遍历行+锁,因为这涉及了undoLog的行为保证.
遇到批量任务时候undoLog可以只是记录任务,
例如:矩形范围内用向量平移了多少多少,而不是逐行记录修改了多少,这样日志和锁可以变少.
这样可以秒速修改全部颜色,线型,图层,矩阵变换...
因此就只能够在底层实现.
提供一个无需保存的策略,直接尾追加日志.
并且可以通过日志回放图形文件,也可以通过图形文件生成日志.
图元类型可以区分成不同的Z序容器,
还可以通过分离"BIM角色"的Z序容器,只是聚合显示.
BIM的求解器惰性执行策略?
区块批量任务可以惰性执行,毕竟日志先行,在查询时候才完成这个任务.
例如旋转两次角度,可以先合并它们,计算就只有一次.
一些补充优化:
LSM树是日志先行,采用惰性写入,它会采用一个无序区先顺序写入行信息,
然后会满了多少之后,合并下一层中,越下层越旧,不是直接写入Z-order排序中.
那么怎么知道数据在一层呢?总不能遍历每一层吧.
指纹跳表:因此会把key做几次hash,写入布隆过滤器.
再查询的时候,就可以并行查询每个层的布隆过滤器.
不过CAD上面完全不需要此类复杂操作.
代码清单:
1,局部锁机制,读写锁,用于更新和插入.
2,全局锁机制,用于全局批量任务执行.还得搞个属性名登记哪些可以批量执行并行SIMD.
3,使用非托管堆创建对象,降低GC压力和STW时间.
双向链表储存区块,索引层就是一个跳表,要放在图元区块最前面,提供给mmap读取层级读取.
4,用图元的中点计算莫顿码.
5,减少区块记录图元类型,不要按照中点混排全部类型图元,而是单独分开储存,
全局批量列式修改时候不需要改图元类型,
按类型分表存储 + 同类数据AoSoA组织,这样检索时候可以并行发送给每个图元容器.
6,采用C#的ZLinq库并行查询,主逻辑用链式调用,调用的函数写有名函数,保证主逻辑简单清晰.
7,分层储存用于渲染优化.
(完) |
|
[复制链接]
发表于 2025-7-20 22:10:25
置顶卡
变色卡
显身卡