平台Linux x86-32 / ELF32NASM 语法全程裸int 0x80syscall不链接 libc。汇编源码内的注释全部使用俄语——纯粹是自我施加的额外难度逼自己在写平衡树逻辑的同时还要用第二语言把每一行的意图讲清楚。全文代码均已在本地用nasm -f elf32汇编、ld -m elf_i386链接、qemu-i386实际运行验证文中贴出的输出都是真实跑出来的不是臆想的伪代码。0. 为什么要干这件事数据结构教科书里B 树永远是稍微复杂一点的那一档它不像链表、栈那样一眼看穿内存布局也不像红黑树那样有大量现成的伪代码可以照抄——CLRS 里的 B-TREE-INSERT、B-TREE-SPLIT-CHILD 是用高级语言的思维写的数组、下标、结构体字段一旦要把它们摊平到寄存器和裸内存地址上会暴露出很多平时被高级语言悄悄兜住的细节节点里到底怎么存孩子指针数组和关键字数组偏移量怎么算会不会算错一个*4没有malloc节点从哪来——自己写一个极简的池分配器递归函数split_child会调insert_nonfullinsert_nonfull又会递归调自己在纯汇编里怎么保证栈平衡、寄存器不被子调用踩掉一个逻辑标志位“是否是叶子节点”如果方向写反,不会报编译错误只会在某次分裂之后安静地把内存踩烂,然后在几百条指令之后才 segfault——这是本文后面会讲的真实翻车现场。这些坑,在 C/C/Python 里几乎不可见,但在汇编里全部会现出原形。写完这一遍之后,对B 树为什么这样设计的理解会比看十遍教科书伪代码更深。1. B 树复习:我们要实现的是什么B 树是一种自平衡的多路搜索树,专为读写块设备场景设计(数据库、文件系统索引都在用)。核心参数是最小度数t,它约束了每个节点能装多少关键字:每个非根节点至少有t - 1个关键字,至多有2t - 1个;每个内部节点的孩子数 关键字数 1,所以孩子数区间是[t, 2t];所有叶子节点深度相同(这是平衡的来源);节点内的关键字始终保持有序,第i个孩子子树里的所有关键字都落在keys[i-1]和keys[i]之间。本文选择t 2,也就是每个节点最多 3 个关键字、最多 4 个孩子——这是能装下的最小非平凡阶数,分裂逻辑最密集,最适合拿来练手(阶数越大,节点内部的搬移代码量越大,但算法逻辑是一样的)。插入的核心技巧是**“预防式分裂”(proactive splitting):不是插入完了发现超员再往回处理,而是自顶向下走的路上,只要即将进入的孩子节点已经满员(n 2t-1),就先把它分裂掉,再决定往左半还是右半继续走。这样保证了整个插入过程是单趟(one-pass)**,不需要任何回溯——这个性质对汇编实现极其友好,因为它意味着我们不需要维护一个父节点栈来做事后调整,递归的天然函数调用栈就够用了。2. 内存布局:节点长什么样没有struct关键字,没有malloc。一切都要自己摆。节点是这样的定长布局(共 36 字节):偏移量 字段 大小 0 leaf 4 字节 ; 1 是叶子, 0 内部节点 4 n 4 字节 ; 当前存了几个关键字 8 keys[0..2] 12 字节 ; 最多 3 个关键字 (2t-1, t2) 20 children[0..3] 16 字节 ; 最多 4 个孩子指针 (2t)为什么不做成变长节点(按实际关键字数分配)?因为变长意味着需要动态内存管理——而这次的自我约束是不依赖标准库、不写通用堆分配器。固定 36 字节的好处是可以用一个静态数组当对象池,分配变成一次乘法加一次加法:%define NODE_SIZE 36 %define MAX_NODES 64 section .bss pool resb NODE_SIZE * MAX_NODES ; узел 36 байт, пул 64 узла next_free resd 1 ; индекс следующего свободного слотаalloc_node就是个 bump allocator——只增不减,没有free(现实中的 B 树删除操作需要回收节点,但这次先只做插入 查找,删除是留给下一篇的坑):; node* alloc_node(void) - eax указатель на новый узел alloc_node: push ebp mov ebp, esp push ebx mov eax, [next_free] ; eax индекс свободного узла mov ebx, eax imul ebx, ebx, NODE_SIZE add ebx, pool ; ebx адрес нового узла inc eax mov [next_free], eax mov eax, ebx mov dword [eax0], 1 ; leaf 1 (истина) по умолчанию — лист mov dword [eax4], 0 ; n 0 (пока нет ключей) pop ebx mov esp, ebp pop ebp ret注意这里一个隐含的设计决策:新分配的节点默认leaf 1。这符合直觉——刚创建出来的节点还没有任何孩子,当然是叶子;只有在它被塞进内部结构、挂上孩子指针之后,才会被显式改成leaf 0(在btree_insert树长高、创建新根的那段代码里能看到)。3. 调用约定与寄存器分配整套代码统一用cdecl 风格手写栈帧:参数从右往左压栈,调用者负责求值顺序,被调用者用ret N自行清栈(这里图省事把调用者/被调用者清栈混用成了被调用者清栈,类似 stdcall,但因为整个工程是自己从头到尾写的,没有和外部 ABI 交互的需求,这样反而少写很多add esp, N);每个函数开头push ebp / mov ebp, esp,参数从[ebp8]开始;需要局部变量就sub esp, N,用[ebp-4]这样的负偏移访问;ebx / ecx / edx / esi / edi但凡会被用到,一律在函数入口 push、出口 pop——这在递归函数里是生死攸关的,因为insert_nonfull会调用自己,split_child里保存的esi(child 指针)如果不被现场保护,递归返回后这个值就废了。eax有意不进入需要保护的名单——它被当作真正意义上的 caller-saved 临时寄存器和返回值寄存器,谁用完就自己再算一次,不指望调用后还保留原值。这是从写了几个版本踩坑之后总结出来的规矩:哪些寄存器跨调用存活、哪些随时可能被冲掉,必须在写代码前就想清楚,而不是出了 bug 再去猜。4. 核心算法:split_child这是全篇最烧脑的一段,把 CLRS 伪代码里数组下标搬移翻译成裸指针运算。逻辑分四步:分配一个新节点z,它将接管child的后半段关键字和孩子指针;把child后t-1个关键字、后t个孩子指针(如果不是叶子的话)搬到z;把parent里i位置之后的孩子指针、关键字统一右移一格,腾出空位;把child的中间关键字提升到parent[i],z挂到parent.children[i1]。; --------------------------------------------------------------------- ; SPLIT_CHILD — расщепление переполненного дочернего узла ; void split_child(node* parent, int i, node* child) ; [ebp8]parent [ebp12]i [ebp16]child ; --------------------------------------------------------------------- split_child: push ebp mov ebp, esp sub esp, 4 ; локальная переменная: указатель на новый узел z push ebx push ecx push edx push esi push edi ; z alloc_node() — новый узел, который заберёт правую половину ключей call alloc_node mov [ebp-4], eax ; сохраняем z mov esi, [ebp16] ; esi child (переполненный узел, 2T-1 ключей) mov edi, [ebp-4] ; edi z (новый узел-сосед) mov eax, [esi0] ; z.leaf child.leaf (наследуем тип узла) mov [edi0], eax mov dword [edi4], T-1 ; z.n T - 1 1 ; копируем старшие ключи child[T..2T-2] - z[0..T-2] ; при T2 копируется ровно один ключ: child.keys[2] - z.keys[0] mov eax, [esi 8 (T)*4] ; child.keys[T] mov [edi 8 0*4], eax ; z.keys[0] ; если child не лист — переносим и указатели на детей [T..2T-1] - z[0..T-1] cmp dword [esi0], 0 ; child.leaf (1 лист, 0 внутренний) jne .skip_children_copy mov eax, [esi 20 (T)*4] ; child.children[T] mov [edi 20 0*4], eax mov eax, [esi 20 (T1)*4] ; child.children[T1] mov [edi 20 1*4], eax .skip_children_copy: mov dword [esi4], T-1 ; child.n T - 1 1 (обрезаем переполненный узел) ; сдвигаем указатели-дети родителя вправо, освобождая место под z: [i1 .. n] mov edx, [ebp8] ; edx parent mov ecx, [edx4] ; ecx parent.n mov eax, [ebp12] ; eax i .shift_children: cmp ecx, eax jle .children_done mov ebx, [edx 20 ecx*4] mov [edx 20 (ecx1)*4], ebx dec ecx jmp .shift_children .children_done: mov ecx, eax inc ecx mov [edx 20 ecx*4], edi ; parent.children[i1] z ; сдвигаем ключи родителя вправо: [i .. n-1] - [i1 .. n] mov ecx, [edx4] dec ecx .shift_keys: cmp ecx, eax jl .keys_done mov ebx, [edx 8 ecx*4] mov [edx 8 (ecx1)*4], ebx dec ecx jmp .shift_keys .keys_done: mov ebx, [esi 8 (T-1)*4] ; средний ключ переносим наверх mov [edx 8 eax*4], ebx inc dword [edx4] ; parent.n 1 pop edi pop esi pop edx pop ecx pop ebx mov esp, ebp pop ebp ret 12这里有个容易踩的雷:.shift_children和.shift_keys两个循环的边界条件不一样——前者是jle(包含等号,因为孩子指针数组要多移一位),后者是jl。CLRS 伪代码里这两个循环的下标范围本来就差一格(孩子比关键字多一个),翻译成汇编时如果偷懒用同一个宏/同一段循环体,边界会全错。这也是为什么最终选择把两段循环完全独立地写开,而不是试图复用——在汇编层面,过早的抽象复用往往比重复代码更容易出 bug。5. insert_nonfull:真正的递归下探insert_nonfull假设自己拿到的节点必然不满(这个前提由调用者保证——正是预防式分裂发挥作用的地方)。它分两种情况:叶子节点:直接在有序位置插入,把后面的关键字整体右移一格;内部节点:找到 key 应该落在哪个孩子的子树里,如果那个孩子已经满员就先分裂它(分裂后中间关键字被提到当前节点,可能导致 key 该走的方向发生变化,所以分裂后要重新比较一次),然后递归调用自己进入那个孩子。; --------------------------------------------------------------------- ; INSERT_NONFULL — вставка ключа в узел, заведомо не полный ; void insert_nonfull(node* x, int key) ; [ebp8]x [ebp12]key ; --------------------------------------------------------------------- insert_nonfull: push ebp mov ebp, esp push ebx push ecx push edx push esi mov esi, [ebp8] ; esi x mov eax, [esi4] ; eax x.n dec eax ; i n - 1 mov ecx, [ebp12] ; ecx key cmp dword [esi0], 0 ; x.leaf ? (1 лист, 0 внутренний узел) jne .leaf_case ; --- ветка внутренний узел --- .find_child_loop: cmp eax, 0 jl .found_child_pos mov edx, [esi 8 eax*4] ; x.keys[i] cmp ecx, edx jge .found_child_pos dec eax jmp .find_child_loop .found_child_pos: inc eax ; i 1 - индекс нужного ребёнка mov ebx, [esi 20 eax*4] ; ebx x.children[i] cmp dword [ebx4], MAX_KEYS ; ребёнок переполнен? jne .no_split_needed push ebx ; child push eax ; i push esi ; parent call split_child ; после расщепления средний ключ мог перегнать наш искомый key mov edx, [esi 8 eax*4] ; x.keys[i] — новый средний ключ cmp ecx, edx jle .no_split_needed inc eax .no_split_needed: mov ebx, [esi 20 eax*4] ; ebx актуальный ребёнок для рекурсии push ecx ; key push ebx ; x ребёнок call insert_nonfull jmp .done .leaf_case: .shift_loop: cmp eax, 0 jl .insert_here mov edx, [esi 8 eax*4] cmp ecx, edx jge .insert_here mov ebx, [esi 8 eax*4] mov [esi 8 (eax1)*4], ebx dec eax jmp .shift_loop .insert_here: inc eax mov [esi 8 eax*4], ecx ; x.keys[i1] key inc dword [esi4] ; x.n 1 .done: pop esi pop edx pop ecx pop ebx mov esp, ebp pop ebp ret 8这里的递归调用call insert_nonfull没有做任何特殊处理——纯汇编的call/ret本身就是一个天然支持递归的机制,只要每次调用都老老实实保护好现场寄存器、维护好栈帧,函数调用自己和调用别的函数在机器层面没有任何区别。这是这次实现里少数几个不需要额外发明轮子的地方。6. btree_insert:树是怎么长高的如果根节点已经满了,不能直接往根里塞——必须先长出一层新根。这是全树唯一会增加高度的时刻:btree_insert: push ebp mov ebp, esp push eax push ebx mov eax, [root] cmp dword [eax4], MAX_KEYS ; корень переполнен? jne .root_not_full call alloc_node mov ebx, eax ; ebx новый корень s mov dword [ebx0], 0 ; s.leaf 0 (это уже не лист) mov dword [ebx4], 0 ; s.n 0 mov eax, [root] mov [ebx 20 0*4], eax ; s.children[0] старый корень mov [root], ebx push eax ; child старый корень push 0 ; i 0 push ebx ; parent s call split_child mov ecx, [ebp8] push ecx push ebx call insert_nonfull jmp .fin .root_not_full: mov ecx, [ebp8] push ecx push eax call insert_nonfull .fin: pop ebx pop eax mov esp, ebp pop ebp ret 47. 真实翻车现场:一个方向反了的 if上面贴出来的代码,其实是修好之后的版本。第一版写完、汇编、链接、丢进qemu-i386跑起来之后,直接是这样:Segmentation fault (core dumped)没有任何输出,连第一行 in-order 遍历的提示语都没打出来。这种完全没输出就死的现场,说明崩溃发生得很早——大概率是第一次调用insert_nonfull或split_child的时候就已经在读写非法地址了。调试思路是把qemu-i386换成静默模式、用nasm -g -F dwarf带上调试信息重新汇编,再对照代码走查每一处涉及leaf字段的分支——这是最值得怀疑的地方,因为它是一个语义方向很容易搞反的布尔值:leaf 1到底该在je还是jne的时候触发对应分支,纯靠肉眼很容易凭感觉写反,而 CPU 不会对你说这个方向感觉不太对。结果真的在三处地方找到了同一个错误的三个变体:; 错误版本(节选自 insert_nonfull): cmp dword [esi0], 0 ; x.leaf ? je .leaf_case ; -- 反了!leaf1 才是叶子,这里却在 leaf0 时跳转leaf字段的约定是1 是叶子。但是je .leaf_case的意思是当[esi0] 0时跳到叶子分支——也就是说,内部节点(leaf0)被当成叶子处理,直接在它的keys数组里插入,完全跳过了找到正确孩子、递归下探的逻辑;而真正的叶子节点反而被当成内部节点,试图读取它本不存在的children指针——那些指针槽位从alloc_node分配出来时是从来没被写过的,里面是.bss段的原始零值或者相邻节点覆盖下来的脏数据,顺着一个野指针写下去,几条指令之后必然SIGSEGV。split_child和inorder_print里也各自藏了一个方向相反的同款错误,因为这三处都是复制粘贴 手改写出来的,复制的时候顺手把判断方向也复制过去了,而三处原本就该是同一个方向。这是一个很有代表性的教训:在没有类型系统兜底的语言里,一个语义相反的分支不会在编译期报错,只会在运行时以完全不相关的症状(内存越界)表现出来,而且离出错的根因(条件反了)往往隔着好几层函数调用,靠 core dump 的崩溃地址反推源头,不如直接把所有同类判断拉出来,一条条对着字段定义重新读一遍来得快。修复方式很朴素——把三处je/jne全部按leaf1表示是叶子这个统一约定改正,同时把原来语焉不详的注释也一并改成明确写出1 лист, 0 внутренний(1叶子,0内部节点),避免未来的自己再犯一次。8. 完整源码以下是通过全部测试的完整实现,包含查找、中序遍历打印和不依赖 libc 的数字转字符串:; ; btree.asm — минимальная реализация B-дерева (степень t 2) ; Платформа: Linux x86-32, ELF32, только сырые syscalls (без libc) ; Автор: neatsuki ; %define T 2 ; минимальная степень дерева %define MAX_KEYS 3 ; 2*T - 1 %define MAX_CHILD 4 ; 2*T %define NODE_SIZE 36 ; 4(leaf) 4(n) 3*4(keys) 4*4(children) %define MAX_NODES 64 ; размер пула узлов (статический аллокатор) section .bss pool resb NODE_SIZE * MAX_NODES ; пул узлов дерева next_free resd 1 ; индекс следующего свободного узла root resd 1 ; указатель на корень дерева numbuf resb 16 ; буфер для перевода числа в строку section .data msg_found db FOUND: len_found equ $ - msg_found msg_notfound db NOT FOUND: len_notfound equ $ - msg_notfound msg_inorder db In-order obhod dereva: , 10 len_inorder equ $ - msg_inorder msg_newline db 10 msg_space db section .text global _start ; void print_str(char *buf, int len) [ebp8]buf [ebp12]len print_str: push ebp mov ebp, esp push eax push ebx push ecx push edx mov eax, 4 ; sys_write mov ebx, 1 ; stdout mov ecx, [ebp8] ; буфер mov edx, [ebp12] ; длина int 0x80 pop edx pop ecx pop ebx pop eax mov esp, ebp pop ebp ret 8 ; void print_num(int n) [ebp8]число (может быть отрицательным) print_num: push ebp mov ebp, esp push eax push ebx push ecx push edx push edi mov eax, [ebp8] lea edi, [numbuf15] ; идём с конца буфера mov byte [edi], 0 mov ebx, 10 xor ecx, ecx ; счётчик цифр test eax, eax jns .conv_loop neg eax ; работаем с модулем, знак допечатаем отдельно .conv_loop: xor edx, edx div ebx ; eax eax/10, edx остаток add dl, 0 dec edi mov [edi], dl inc ecx test eax, eax jnz .conv_loop mov eax, [ebp8] test eax, eax jns .no_sign dec edi mov byte [edi], - inc ecx .no_sign: push ecx push edi call print_str pop edi pop ecx pop edx pop ebx pop eax mov esp, ebp pop ebp ret 4 ; node* alloc_node(void) - eax указатель на новый узел alloc_node: push ebp mov ebp, esp push ebx mov eax, [next_free] mov ebx, eax imul ebx, ebx, NODE_SIZE add ebx, pool inc eax mov [next_free], eax mov eax, ebx mov dword [eax0], 1 ; leaf 1 по умолчанию mov dword [eax4], 0 ; n 0 pop ebx mov esp, ebp pop ebp ret ; void split_child(node* parent, int i, node* child) split_child: push ebp mov ebp, esp sub esp, 4 push ebx push ecx push edx push esi push edi call alloc_node mov [ebp-4], eax mov esi, [ebp16] mov edi, [ebp-4] mov eax, [esi0] mov [edi0], eax mov dword [edi4], T-1 mov eax, [esi 8 (T)*4] mov [edi 8 0*4], eax cmp dword [esi0], 0 jne .skip_children_copy mov eax, [esi 20 (T)*4] mov [edi 20 0*4], eax mov eax, [esi 20 (T1)*4] mov [edi 20 1*4], eax .skip_children_copy: mov dword [esi4], T-1 mov edx, [ebp8] mov ecx, [edx4] mov eax, [ebp12] .shift_children: cmp ecx, eax jle .children_done mov ebx, [edx 20 ecx*4] mov [edx 20 (ecx1)*4], ebx dec ecx jmp .shift_children .children_done: mov ecx, eax inc ecx mov [edx 20 ecx*4], edi mov ecx, [edx4] dec ecx .shift_keys: cmp ecx, eax jl .keys_done mov ebx, [edx 8 ecx*4] mov [edx 8 (ecx1)*4], ebx dec ecx jmp .shift_keys .keys_done: mov ebx, [esi 8 (T-1)*4] mov [edx 8 eax*4], ebx inc dword [edx4] pop edi pop esi pop edx pop ecx pop ebx mov esp, ebp pop ebp ret 12 ; void insert_nonfull(node* x, int key) insert_nonfull: push ebp mov ebp, esp push ebx push ecx push edx push esi mov esi, [ebp8] mov eax, [esi4] dec eax mov ecx, [ebp12] cmp dword [esi0], 0 jne .leaf_case .find_child_loop: cmp eax, 0 jl .found_child_pos mov edx, [esi 8 eax*4] cmp ecx, edx jge .found_child_pos dec eax jmp .find_child_loop .found_child_pos: inc eax mov ebx, [esi 20 eax*4] cmp dword [ebx4], MAX_KEYS jne .no_split_needed push ebx push eax push esi call split_child mov edx, [esi 8 eax*4] cmp ecx, edx jle .no_split_needed inc eax .no_split_needed: mov ebx, [esi 20 eax*4] push ecx push ebx call insert_nonfull jmp .done .leaf_case: .shift_loop: cmp eax, 0 jl .insert_here mov edx, [esi 8 eax*4] cmp ecx, edx jge .insert_here mov ebx, [esi 8 eax*4] mov [esi 8 (eax1)*4], ebx dec eax jmp .shift_loop .insert_here: inc eax mov [esi 8 eax*4], ecx inc dword [esi4] .done: pop esi pop edx pop ecx pop ebx mov esp, ebp pop ebp ret 8 ; void btree_insert(int key) btree_insert: push ebp mov ebp, esp push eax push ebx mov eax, [root] cmp dword [eax4], MAX_KEYS jne .root_not_full call alloc_node mov ebx, eax mov dword [ebx0], 0 mov dword [ebx4], 0 mov eax, [root] mov [ebx 20 0*4], eax mov [root], ebx push eax push 0 push ebx call split_child mov ecx, [ebp8] push ecx push ebx call insert_nonfull jmp .fin .root_not_full: mov ecx, [ebp8] push ecx push eax call insert_nonfull .fin: pop ebx pop eax mov esp, ebp pop ebp ret 4 ; node* btree_search(node* x, int key) - eax узел или 0 btree_search: push ebp mov ebp, esp push ebx push ecx push edx push esi mov esi, [ebp8] mov ecx, [ebp12] xor eax, eax .search_loop: cmp eax, [esi4] jge .after_loop mov edx, [esi 8 eax*4] cmp ecx, edx jle .after_loop inc eax jmp .search_loop .after_loop: cmp eax, [esi4] jge .not_this_key mov edx, [esi 8 eax*4] cmp ecx, edx jne .not_this_key mov eax, esi jmp .ret_found .not_this_key: cmp dword [esi0], 0 jne .not_found mov ebx, [esi 20 eax*4] push ecx push ebx call btree_search jmp .ret_found .not_found: xor eax, eax .ret_found: pop esi pop edx pop ecx pop ebx mov esp, ebp pop ebp ret 8 ; void inorder_print(node* x) inorder_print: push ebp mov ebp, esp push ebx push ecx push esi mov esi, [ebp8] xor ecx, ecx .walk_loop: cmp ecx, [esi4] jg .walk_done cmp dword [esi0], 0 jne .print_key push ecx mov ebx, [esi 20 ecx*4] push ebx call inorder_print pop ecx .print_key: cmp ecx, [esi4] jge .walk_next push ecx mov ebx, [esi 8 ecx*4] push ebx call print_num push 1 push msg_space call print_str pop ecx .walk_next: inc ecx jmp .walk_loop .walk_done: pop esi pop ecx pop ebx mov esp, ebp pop ebp ret 4 ; ; ТОЧКА ВХОДА ; _start: mov dword [next_free], 0 call alloc_node mov [root], eax push 10 call btree_insert push 20 call btree_insert push 5 call btree_insert push 6 call btree_insert push 12 call btree_insert push 30 call btree_insert push 7 call btree_insert push 17 call btree_insert push msg_inorder mov eax, len_inorder push eax call print_str mov eax, [root] push eax call inorder_print push 1 push msg_newline call print_str push len_found push msg_found call print_str mov eax, [root] push 17 push eax call btree_search test eax, eax setnz al movzx eax, al push eax call print_num push 1 push msg_newline call print_str push len_notfound push msg_notfound call print_str mov eax, [root] push 99 push eax call btree_searc
