# Index Concurrency Control 在前两节中讨论的数据结构中，我们都只考虑单线程访问的情况。实践中，绝大多数情况下，我们需要在并发访问情况下保证我们的数据结构还能够正常工作。除了 VoltDB，它用一个线程处理所有请求，彻底排除了并发的需要。 ## Concurrency Control 通常我们会从两个层面上来理解并发控制的正确性： * Logical Correctness：（17 节）我是否能看到我应该要看到的数据？ * Physical Correctness：（本节）数据的内部表示是否安好？ ### 本节大纲： * Latch Modes * Index Crabbing/Coupling * Leaf Scans * Delayed Parent Updates ## Latch Modes #### Read Mode * 多个线程可以同时读取相同的数据 * 针对相同的数据，当别的线程已经获得处于 read mode 的 latch，新的线程也可以继续获取 read mode 的 latch #### Write Mode * 同一时间只有单个线程可以访问 * 针对相同的数据，如果获取前已经有别的线程获得任何 mode 的 latch，新的线程就无法获取 write mode 的 latch ## B+ Tree Concurrency Control 我们希望在最大程度上允许多个线程同时读取、更新同一个 B+ Tree index，主要需要考虑两种情况： * 多个线程同时修改同一个 node * 一个线程正在遍历 B+ Tree 的同时，另一个线程正在 splits/merges nodes 举例如下： ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_DUCROVIbhSplr2Eo6%2F-L_DV_tT526tMb37s8Yx%2FScreen%20Shot%202019-03-05%20at%2011.39.11%20PM.jpg?alt=media\&token=29af249a-a9d2-49e0-8136-5dd2eec8036b) T1 想要删除 44，T2 想要查询 41。删除 44 时，DBMS 需要 rebalance D 节点，将 H 节点拆分成两个节点。若在拆分前，T2 读取到 D 节点，发现 41 在 H 节点，此时时间片轮转到了 T1，T1 把 D 节点拆分成 H、I 两个节点，同时把 41 转移到 I 节点，之后 CPU 交还给 T2，T2 到 H 节点就找不到 41，如下图所示： ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_DUCROVIbhSplr2Eo6%2F-L_DVF0MYiTsWD9iqtiV%2FScreen%20Shot%202019-03-05%20at%2011.37.36%20PM.jpg?alt=media\&token=c8ac0cc2-b088-4c14-9a33-709d554334b4) 如何解决该问题？由于 B+ Tree 是树状结构，有明确的访问顺序，因此很容易想到沿着访问路径加锁的方法，即 Latch Crabbing/Coupling ### Latch Crabbing/Coupling Latch Crabbing 的基本思想如下： * 获取 parent 的 latch * 获取 child 的 latch * 如果***安全***，则可以释放 parent 的 latch 这里的“安全”指的是，当发生更新操作时，该节点不会发生 split 或 merge 的操作，即： * 在插入元素时，节点未满 * 在删除元素时，节点超过半满 #### Search 从 root 往下，不断地： * 获取 child 的 read latch * 释放 parent 的 read latch 举例如下：Search 38 ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_DUCROVIbhSplr2Eo6%2F-L_DYoD433UgUgaQbHwe%2FScreen%20Shot%202019-03-05%20at%2011.53.16%20PM.jpg?alt=media\&token=0611e7e2-0b91-4e6a-b546-8a6b44767e75) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_DUCROVIbhSplr2Eo6%2F-L_DYsvqHdQzoya7pjj1%2FScreen%20Shot%202019-03-05%20at%2011.53.37%20PM.jpg?alt=media\&token=e8b2b5a3-e8e6-4b37-b9a2-b21a294b0989) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_DUCROVIbhSplr2Eo6%2F-L_DYxTzgPQOGenqWcFR%2FScreen%20Shot%202019-03-05%20at%2011.53.55%20PM.jpg?alt=media\&token=07c161e8-8d47-4f90-b61b-b7e436366b39) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_DUCROVIbhSplr2Eo6%2F-L_DZ13egH9rrJkRhgGu%2FScreen%20Shot%202019-03-05%20at%2011.54.15%20PM.jpg?alt=media\&token=0bdcad23-51c5-482d-90e8-285347ea8647) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_DUCROVIbhSplr2Eo6%2F-L_DZ73JZvGSVmq2NryE%2FScreen%20Shot%202019-03-05%20at%2011.54.34%20PM.jpg?alt=media\&token=6d4880d8-b5a9-4204-abd2-a8b72b6281ef) #### Insert/Delete 从 root 往下，按照需要获取 write latch，一旦获取了 child 的 write latch，检查它是否安全，如果安全，则释放之前获取的所有 write latch。 例 1 如下：Delete 38 ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_DUCROVIbhSplr2Eo6%2F-L_DZPQao5pTG0V-rkal%2FScreen%20Shot%202019-03-05%20at%2011.55.54%20PM.jpg?alt=media\&token=176df9a2-8179-4466-824f-5511da6e28b5) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_DUCROVIbhSplr2Eo6%2F-L_DZUFCC557WpQ0xiOs%2FScreen%20Shot%202019-03-05%20at%2011.56.13%20PM.jpg?alt=media\&token=87ac25d0-2ffe-4f45-baf0-f4be24d2e514) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_DUCROVIbhSplr2Eo6%2F-L_DZaTDO794EM7WX-sx%2FScreen%20Shot%202019-03-05%20at%2011.56.43%20PM.jpg?alt=media\&token=a7b56e8f-e2af-457e-9050-60bd0ca22764) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_DUCROVIbhSplr2Eo6%2F-L_DZiCVUCje9HjTO-fP%2FScreen%20Shot%202019-03-05%20at%2011.57.14%20PM.jpg?alt=media\&token=4dcda510-d7ca-44db-a7ce-e7f2ae5dbc20) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_DUCROVIbhSplr2Eo6%2F-L_DZoWD0V2eGPVpBQCR%2FScreen%20Shot%202019-03-05%20at%2011.57.37%20PM.jpg?alt=media\&token=fb73169b-63f8-443f-a3d2-e822021cfe6f) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_DUCROVIbhSplr2Eo6%2F-L_D_IsLUJovGgB_28fo%2FScreen%20Shot%202019-03-05%20at%2011.59.49%20PM.jpg?alt=media\&token=caa21f75-2e88-41c7-84c8-b7bf93b00245) 例 2 如下：Insert 45 ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_DUCROVIbhSplr2Eo6%2F-L_D_cGh7PFgdsPWVEKy%2FScreen%20Shot%202019-03-06%20at%2012.01.13%20AM.jpg?alt=media\&token=45b43fe9-2e72-441c-9504-5b72170e5c40) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_DUCROVIbhSplr2Eo6%2F-L_D_kHAAdtorfsq4gNM%2FScreen%20Shot%202019-03-06%20at%2012.01.45%20AM.jpg?alt=media\&token=e1cf66b2-fb3c-4237-8494-0efca991fee8) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_DUCROVIbhSplr2Eo6%2F-L_D_oWAJbDbHHA36cm0%2FScreen%20Shot%202019-03-06%20at%2012.02.03%20AM.jpg?alt=media\&token=1e3f482a-4835-40c1-aaa9-084ef9cec5ac) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_DUCROVIbhSplr2Eo6%2F-L_D_uzqhJMGdNgJXC4k%2FScreen%20Shot%202019-03-06%20at%2012.02.28%20AM.jpg?alt=media\&token=3c874da7-c3ee-4a47-8a3a-43b56712473e) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_DUCROVIbhSplr2Eo6%2F-L_D_zcsb1G_n-lL0UWF%2FScreen%20Shot%202019-03-06%20at%2012.02.47%20AM.jpg?alt=media\&token=257fcfed-1f0b-4911-8354-b71289bb759e) 例 3：Insert 25 ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_DUCROVIbhSplr2Eo6%2F-L_DaA7Ey04vDM9NceNx%2FScreen%20Shot%202019-03-06%20at%2012.03.36%20AM.jpg?alt=media\&token=c51ff72c-bb98-4bd8-832f-5a649d588597) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_DUCROVIbhSplr2Eo6%2F-L_DaEwuxQ3apU-rSJXS%2FScreen%20Shot%202019-03-06%20at%2012.03.55%20AM.jpg?alt=media\&token=05fe461d-e047-42ea-a892-8065cda21fea) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_DUCROVIbhSplr2Eo6%2F-L_DaJZBHE-13w2RvuyS%2FScreen%20Shot%202019-03-06%20at%2012.04.13%20AM.jpg?alt=media\&token=a96831e1-d1c7-4f84-a8ce-95277459a7ab) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_DUCROVIbhSplr2Eo6%2F-L_DaNg_9tRVu7tENaU_%2FScreen%20Shot%202019-03-06%20at%2012.04.31%20AM.jpg?alt=media\&token=f9995ea2-74d9-40ea-aa50-131c589c1a97) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_DUCROVIbhSplr2Eo6%2F-L_DaSsennVpIB5Mm5s0%2FScreen%20Shot%202019-03-06%20at%2012.04.51%20AM.jpg?alt=media\&token=5e60b1cf-bdc2-409d-a660-91c2d677f23d) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_DUCROVIbhSplr2Eo6%2F-L_DaZ8reSqVj3Do_R7h%2FScreen%20Shot%202019-03-06%20at%2012.05.18%20AM.jpg?alt=media\&token=756b9f75-1790-40b8-bea5-db6dbf32f7f0) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_DUCROVIbhSplr2Eo6%2F-L_Dacx04-MRg935Naf2%2FScreen%20Shot%202019-03-06%20at%2012.05.36%20AM.jpg?alt=media\&token=5247e969-8267-4d1a-bd70-818961fc9f54) ### Better Latching Algorithm 在实际应用中： * 更新操作每次都需要在路径上获取 write latch 容易成为系统并发瓶颈 * 通常 Node 的大小为一个 page，可以存储很多 keys，因此更新操作的出现频率不算高 我们能否在 Latch Crabbing 的基础上做得更好？ 可以采用类似乐观锁的思想，假设 leaf node 是安全（更新操作仅会引起 leaf node 的变化）的，在查询路径上一路获取、释放 read latch，到达 leaf node 时，若操作不会引起 split/merge 发生，则只需要在 leaf node 上获取 write latch 然后更新数据，释放 write latch 即可；若操作会引起 split/merge 发生，则重新执行一遍，此时在查询路径上一路获取、释放 write latch，即 Latch Crabbing 原始方案。 举例：Delete 38 ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_GDzslSxoCt8--keMN%2F-L_GGE6wjo3z5rM-T7_4%2FScreen%20Shot%202019-03-06%20at%2012.30.59%20PM.jpg?alt=media\&token=10b6a2dc-8caa-4408-b874-4747b6ba68bf) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_GDzslSxoCt8--keMN%2F-L_GGIDQ9aPavzNUSBhh%2FScreen%20Shot%202019-03-06%20at%2012.31.16%20PM.jpg?alt=media\&token=767f148f-c47a-49bf-ac58-9c23fb2b334e) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_GDzslSxoCt8--keMN%2F-L_GGMcQDKDZ-az_Alci%2FScreen%20Shot%202019-03-06%20at%2012.31.31%20PM.jpg?alt=media\&token=bbac79b5-f472-4b7c-bf57-17ae8b041ea4) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_GDzslSxoCt8--keMN%2F-L_GGQY0sv9c7JaZt0pr%2FScreen%20Shot%202019-03-06%20at%2012.31.49%20PM.jpg?alt=media\&token=80d957a2-b443-4a94-b09e-203e4bf5b2d8) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_GDzslSxoCt8--keMN%2F-L_GGV2EJzM8dLCC9um6%2FScreen%20Shot%202019-03-06%20at%2012.32.07%20PM.jpg?alt=media\&token=afaadd56-e403-44fe-ba25-b4764c1e9918) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_GDzslSxoCt8--keMN%2F-L_GGaH98oZ83IAgp3Dz%2FScreen%20Shot%202019-03-06%20at%2012.32.34%20PM.jpg?alt=media\&token=2557fe69-a99a-497d-8942-12ef9c03e618) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_GDzslSxoCt8--keMN%2F-L_GGfpxVWwbR7UUOufR%2FScreen%20Shot%202019-03-06%20at%2012.32.57%20PM.jpg?alt=media\&token=872de434-06b4-485e-8fbb-c242906b2607) #### Better Latching Algorithm 小结 * Search：与 Latch Crabbing 相同 * Insert/Delete: * 使用与 Search 相同的方式在查询路径上获取、释放 latch，在 leaf node 上获取 write latch * 如果 leaf node 不安全，可能会引起其它节点的变动，则使用 Latch Crabbing 的策略再执行一遍 该方法乐观地假设整个操作只会引起 leaf node 的变化，若假设错误，则使用 Latch Crabbing 的原始方案。 ### Horizontal Scan 之前的分析中我们仅仅关注了从上到下的访问模式，而没有考虑到左右方向的访问模式，在 range query 中，常常需要横向访问相邻的 nodes。 例1：T1: Find Keys < 4 ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_GDzslSxoCt8--keMN%2F-L_GIK6BxfxYVy1jWIfS%2FScreen%20Shot%202019-03-06%20at%2012.39.48%20PM.jpg?alt=media\&token=f59fbd3a-9ffb-4ac2-9c4e-29b6218abb02) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_GDzslSxoCt8--keMN%2F-L_GINosGE2fwYVU3QsL%2FScreen%20Shot%202019-03-06%20at%2012.40.23%20PM.jpg?alt=media\&token=1437777e-c05e-490e-baa0-515bf1a6544b) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_GDzslSxoCt8--keMN%2F-L_GIS46FdXYaOULCDAa%2FScreen%20Shot%202019-03-06%20at%2012.40.41%20PM.jpg?alt=media\&token=4db813f9-76f1-4ce4-a6cb-4274d0cab5aa) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_GDzslSxoCt8--keMN%2F-L_GIXAbBqVKR6-yd52X%2FScreen%20Shot%202019-03-06%20at%2012.41.01%20PM.jpg?alt=media\&token=bdeec956-c5c3-4dcf-a6d4-7ba94258b4b8) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_GDzslSxoCt8--keMN%2F-L_GI_qIgogjtJBIC-EX%2FScreen%20Shot%202019-03-06%20at%2012.41.16%20PM.jpg?alt=media\&token=061c50ae-b953-4137-ac48-3ad50bb46d98) 如果此时刚好有另一个线程作相反方向的访问：T2: Find Keys > 1： ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_GDzslSxoCt8--keMN%2F-L_GJ0xlbj6jjhobhDKx%2FScreen%20Shot%202019-03-06%20at%2012.43.12%20PM.jpg?alt=media\&token=0552a891-8c56-4d9b-a074-e785518f1b07) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_GDzslSxoCt8--keMN%2F-L_GJ4_GP48w_PRh9G0L%2FScreen%20Shot%202019-03-06%20at%2012.43.26%20PM.jpg?alt=media\&token=fd68092c-b903-475e-abb0-ce40a3bb8c89) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_GDzslSxoCt8--keMN%2F-L_GJBlzSLrXOOYpiiF9%2FScreen%20Shot%202019-03-06%20at%2012.43.56%20PM.jpg?alt=media\&token=97fee3d2-09ad-4f2d-a788-60815c71a524) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_GDzslSxoCt8--keMN%2F-L_GJFjSEnpVJe8EgtGu%2FScreen%20Shot%202019-03-06%20at%2012.44.13%20PM.jpg?alt=media\&token=510e6121-4f15-46dd-8f45-e49b48fe418a) 由于 read latch 允许被多次获取，因此并发读的情况不会产生负面影响。 例 2：T1: Delete 4，T2: Find Keys > 1 ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_GDzslSxoCt8--keMN%2F-L_GJ_Q66CTHqFc4eG5K%2FScreen%20Shot%202019-03-06%20at%2012.45.37%20PM.jpg?alt=media\&token=82ef0131-2a44-4d93-a0e3-7bcdeaedb1b2) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_GDzslSxoCt8--keMN%2F-L_GJeEmwL75d9UwCVyU%2FScreen%20Shot%202019-03-06%20at%2012.45.57%20PM.jpg?alt=media\&token=16e6d50c-75cd-4c82-ad1f-3a1a8d148d70) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_GDzslSxoCt8--keMN%2F-L_GJhn4apCKL3f4uFu9%2FScreen%20Shot%202019-03-06%20at%2012.46.11%20PM.jpg?alt=media\&token=6d451834-711e-4a95-885a-3c334651cd7e) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_GDzslSxoCt8--keMN%2F-L_GJmfevcs4JFNYJ_8i%2FScreen%20Shot%202019-03-06%20at%2012.46.26%20PM.jpg?alt=media\&token=2ef5dcd0-dbad-4521-b602-5e82c1e135b0) 当遇到横向扫描无法获取下一个节点的 latch 时，该线程将释放 latch 后自杀。这种策略逻辑简单，尽管有理论上的优化空间，但在实践中是常见的避免死锁的方式。 ### Delayed Parent Updates 从上文中，我们可以观察到：每当 leaf node 溢出时，我们都需要更新至少 3 个节点： * 即将被拆分的 leaf node * 新的 leaf node * parent node 修改的成本较高，因此 B-link Tree 提出了一种优化策略：每当 leaf node 溢出时，只是标记一下而暂时不更新 parent node，等下一次有别的线程获取 parnet node 的 write latch 时，一并修改。 举例如下：Insert 25 ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_GDzslSxoCt8--keMN%2F-L_GLhe5dLXhoZDVLrbG%2FScreen%20Shot%202019-03-06%20at%2012.54.55%20PM.jpg?alt=media\&token=805dba26-ed15-458d-b2bf-e4b1a09677fb) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_GDzslSxoCt8--keMN%2F-L_GLlSaNU9iAtS-vXYc%2FScreen%20Shot%202019-03-06%20at%2012.55.11%20PM.jpg?alt=media\&token=16ef1697-5a3f-4815-b2d5-a7e916464baf) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_GDzslSxoCt8--keMN%2F-L_GLpJnUC_UAaIpc4XF%2FScreen%20Shot%202019-03-06%20at%2012.55.26%20PM.jpg?alt=media\&token=a5e1b440-bc0d-47e3-88e5-6d6c1f375be1) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_GDzslSxoCt8--keMN%2F-L_GLtMpUl7HSTTCPcys%2FScreen%20Shot%202019-03-06%20at%2012.55.43%20PM.jpg?alt=media\&token=c9ee92e0-cf83-4691-b090-4335b60d7ae9) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_GDzslSxoCt8--keMN%2F-L_GLxXjX0uv5enS6YVJ%2FScreen%20Shot%202019-03-06%20at%2012.56.00%20PM.jpg?alt=media\&token=32087b51-5907-41b7-b821-f471e61f342c) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_GDzslSxoCt8--keMN%2F-L_GM0YkZQzKWPpIhEjQ%2FScreen%20Shot%202019-03-06%20at%2012.56.16%20PM.jpg?alt=media\&token=0868efd1-3e65-4801-92c6-4560054356ff) ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-L_GDzslSxoCt8--keMN%2F-L_GM586KEYFngym07la%2FScreen%20Shot%202019-03-06%20at%2012.56.31%20PM.jpg?alt=media\&token=c612c534-8269-4a51-b9f5-6bbc502b2239) Delayed Parent Updates 仅用在 insert 操作中。 ## Conclusion 让一个数据结构具备并发安全的特点知难行易，尽管本节只是介绍 B+ Tree 上的相关技术，但这些技术同样适用于其他数据结构。 ## 参考 [slides](https://15445.courses.cs.cmu.edu/fall2018/slides/09-indexconcurrency.pdf)