flowchart TD A[TryOptimisticInsert] --> B[Read header and get root id] B --> C{root invalid?} C -- yes --> R[Return nullopt: restart pessimistic] C -- no --> D[Read-crab from root to target leaf] D --> E[Remember leaf page id and route bounds] E --> F[Drop leaf read latch] F --> G[Write latch same leaf page] G --> H{leaf still matches key route?} H -- no --> R H -- yes --> I{key physically exists?} I -- yes --> J{key tombstoned?} J -- no --> K[Return false: duplicate key] J -- yes --> L[Remove tombstone and overwrite value] L --> M[Return true] I -- no --> N{leaf size < max size?} N -- yes --> O[Insert into leaf] O --> M N -- no --> R
flowchart TD A[InsertPessimistic] --> B[Write latch header page] B --> C{root invalid?} C -- yes --> D[New root leaf page] D --> E[Insert first key into root leaf] E --> F[Update header.root_page_id] F --> Z[Return true] C -- no --> G[Write latch root page] G --> H{current is leaf?} H -- no --> I[Push current guard into ctx.write_set] I --> J[Write latch child page] J --> H H -- yes --> K[Check duplicate or tombstone resurrection] K --> L{leaf has space?} L -- yes --> M[Insert into leaf] M --> Z L -- no --> N[Split leaf] N --> O[Propagate separator upward with ctx.write_set] O --> P{reach old root?} P -- no --> Q[Insert or split parent] Q --> O P -- yes --> R[Create new root internal] R --> S[Update header.root_page_id through ctx.header_page] S --> Z
乐观删除
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
flowchart TD A[TryOptimisticRemove] --> B[Read header and get root id] B --> C{root invalid?} C -- yes --> D[Return true: already empty] C -- no --> E[Read-crab from root to target leaf] E --> F[Remember leaf id and route bounds] F --> G[Drop leaf read latch] G --> H[Write latch same leaf] H --> I{leaf still matches key route?} I -- no --> R[Return false: restart pessimistic] I -- yes --> J{key exists and not tombstoned?} J -- no --> K[Return true: nothing to delete] J -- yes --> L{DeleteWouldStayLeafLocal?} L -- no --> R L -- yes --> M[Add tombstone or local physical remove] M --> N[Return true]
flowchart TD A[RemovePessimistic] --> B[Write latch header page] B --> C{root invalid?} C -- yes --> Z[Return] C -- no --> D[Write latch root page] D --> E{current is leaf?} E -- no --> F[Push current guard into ctx.write_set] F --> G[Write latch child page] G --> E E -- yes --> H{key exists and not tombstoned?} H -- no --> Z H -- yes --> I[Add tombstone] I --> J{physical remove happened?} J -- no --> Z J -- yes --> K{leaf size >= min size?} K -- yes --> L{first physical key changed?} L -- yes --> M[Update separator by CheckRouteKey] L -- no --> Z M --> Z K -- no --> N{leaf is root?} N -- yes --> O{root leaf empty?} O -- yes --> P[header.root_page_id = INVALID] O -- no --> Z P --> Z N -- no --> Q[HandleLeafUnderflow] Q --> Z