【07】分布式事務解決方案

1、事務簡介

  • 事務(Transaction)是訪問并可能更新數據庫中各種數據項的一個程序執行單元(unit)。
  • 在關系數據庫中,一個事務由一組SQL語句組成。事務應該具有ACID四個特性:原子性一致性隔離性持久性
  • 任何事務機制在實現時,都應該考慮事務的ACID特性,包括:本地事務、分布式事務。

1.1 本地事務

  • @Transational
    • 大多數場景下,我們的應用都只需要操作單一的數據庫,這種情況下的事務稱之為本地事務(Local Transaction)。本地事務的ACID特性是數據庫直接提供支持。
    • 本地事務應用架構如下所示:
      本地事務架構圖
  • 在JDBC編程中,我們通過java.sql.Connection對象來開啟、關閉或者提交事務。
    • 代碼如下所示:
      Connection conn = ... //獲取數據庫連接
      conn.setAutoCommit(false); //開啟事務
      try{//...執行增刪改查sqlconn.commit(); //提交事務
      }catch (Exception e) {conn.rollback();//事務回滾
      }finally{conn.close();//關閉鏈接
      

1.2 分布式事務典型場景

  • 當下互聯網發展如火如荼,絕大部分公司都進行了數據庫拆分和服務化(SOA)。在這種情況下,完成某一個業務功能可能需要橫跨多個服務,操作多個數據庫。
  • 這就涉及到了分布式事務,需要操作的資源位于多臺資源服務器上,而應用需要保證對于多個資源服務器數據的操作,要么全部成功,要么全部失敗。本質上來說,分布式事務就是為了保證不同資源服務器的數據一致性。
1.2.1 跨庫事務
  • 跨庫事務指的是,應用的某個功能需要操作多個庫,不同的庫中存儲這不同的業務數據。
  • 下圖演示了一個服務同時操作兩個庫的情況:
    跨庫事務
1.2.2 分庫分表
  • 通常一個庫數據量比較大或者預期未來的數據量比較大,都會進行水平拆分,也就是分庫分表。
  • 如下圖,將數據庫B拆分成了2個庫:
    分庫分表
  • 對于分庫分表的情況,一般開發人員都會使用一些數據庫中間件來降低sql操作的復雜性
  • 例如,對于sql:insert into user(id,name) values (1,"張三"),(2,"李四")。這條sql是操作單庫的語法,單庫情況下,可以保證事務的一致性。
  • 但是由于現在進行了分庫分表,開發人員希望將1號記錄插入分庫1,2號記錄插入分庫2。所以數據庫中間件要將其改寫為2條sql,分別插入兩個不同的分庫,此時要保證兩個庫要不都成功,要不都失敗,因此基本上所有的數據庫中間件都面臨著分布式事務的問題。
1.2.3 服務化
  • 微服務架構是目前比較比較火的概念。例如:某個應用同時操作了9個數據庫,這樣的應用業務邏輯必然非常復雜,對于開發人員是極大的挑戰,應該拆分成不同的獨立服務,以簡化業務邏輯。拆分后,獨立服務之間通過RPC框架來進行遠程調用,實現彼此的通信。
  • 下圖演示了3個服務之間彼此調用的架構:
    服務化
  • Service A完成某個功能需要直接操作數據庫,同時又需要調用Service B和Service C,而Service B又同時操作了2個數據庫,Service C也操作了一個庫。需要保證這些跨服務的對多個數據庫的操作要不都成功,要不都失敗,實際上這可能是最典型的分布式事務場景。

2、分布式事務理論基礎

  • 解決分布式事務,也有相應的規范和協議。分布式事務相關的協議有2PC3PC
  • 由于3PC(三階段提交協議)非常難實現,目前市面主流的分布式事務解決方案都是2PC協議。
  • 有些文章在分析2PC時,幾乎都會用TCC兩階段的例子,第一階段try,第二階段完成confirm或cancel。其實2PC并不是專為實現TCC設計的,2PC具有普適性——協議一樣的存在,目前絕大多數分布式解決方案都是以2PC(兩階段提交協議)為基礎的。
  • TCC(Try-Confirm-Cancel) 實際上是服務化的兩階段提交協議。

2.1 2PC兩階段提交協議

  • 2PC(Two-Prepare-Commit):分為Prepare(預處理)和Commit(提交)兩個階段。
    • Prepare:提交事務請求
      prepare
      • 首先協調者向所有參與者發送事務請求,詢問是否可以執行事務操作,然后等待各個參與者的響應;
      • 然后:各個參與者接收到協調者事務請求后,執行事務操作(例如:更新一個關系型數據庫表中的記錄),并將 Undo(更新前的狀態) 和 Redo(更新后的狀態) 信息記錄事務日志中。
      • 最后:如果參與者成功執行了事務并寫入 Undo 和 Redo 信息,則向協調者返回 YES 響應,否則返回 NO 響應。當然,參與者也可能宕機,從而不會返回響應。
    • Commit:執行事務提交/回滾
    • 正常提交事務:
      正常事務提交
      • 首先:協調者向所有參與者發送 Commit 請求。
      • 然后:參與者收到 Commit 請求后,執行事務提交,提交完成后釋放事務執行期占用的所有資源。
      • 其次:參與者執行事務提交后向協調者發送 Ack 反饋響應。
      • 最后:協調者接收到所有參與者的 Ack 響應后,完成事務提交。
    • 回滾事務:
      • 在執行 Prepare 步驟過程中,如果某些參與者執行事務失敗、宕機或與協調者之間的網絡中斷,那么協調者就無法收到所有參與者的 YES 響應,或者某個參與者返回了 No 響應,此時,協調者就會進入回退流程,對各個參與者的事務進行回滾操作。
        回滾事務
      • 首先:協調者向所有參與者發送 Rollback 請求。
      • 然后:參與者收到 Rollback 后,使用 Prepare 階段的 Undo 日志執行事務回滾,完成后釋放事務執行期占用的所有資源。
      • 其次: 參與者執行事務回滾后向協調者發送 Ack 響應。
      • 最后:接收到所有參與者的 Ack 響應后,完成事務回滾。

2.2 2PC存在的問題

  • 同步阻塞:參與者在等待協調者的指令時,其實是在等待其他參與者的響應,在此過程中,參與者是無法進行其他操作的,也就是阻塞了其運行。 倘若參與者與協調者之間網絡異常導致參與者一直收不到協調者信息,那么會導致參與者一直阻塞下去。
  • 單點障礙:在 2PC 中,一切請求都來自協調者,所以協調者的地位是至關重要的,如果協調者宕機,那么就會使參與者一直阻塞并一直占用事務資源。
  • 數據不一致:Commit 事務過程中,Commit 請求 或 Rollback 請求可能會因為協調者宕機或協調者與參與者網絡問題丟失,那么就導致了部分參與者沒有收到 Commit/Rollback 請求,而其他參與者則正常收到執行了 Commit/Rollback 操作,沒有收到請求的參與者則繼續阻塞。這時,參與者之間的數據就不再一致了。
  • 環境可靠性依賴:協調者 Prepare 請求發出后,等待響應,然而如果有參與者宕機或與協調者之間的網絡中斷,都會導致協調者無法收到所有參與者的響應,那么在 2PC 中,協調者會等待一定時間,然后超時后,會觸發事務中斷,在這個過程中,協調者和所有其他參與者都是出于阻塞的。這種機制對網絡問題常見的現實環境來說太苛刻了。

3、分布式事務實現的4種模式

3.1 AT模式(auto transcation)

  • AT 模式是一種無侵入的分布式事務解決方案,阿里的Seata框架,實現了該模式。
  • 在 AT 模式下,用戶只需關注自己的“業務 SQL”,用戶的 “業務 SQL” 作為一階段,Seata 框架會自動生成事務的二階段進行提交和回滾操作。
    階段圖
  • AT 模式如何做到對業務的無侵入 :
    • AT 模式的一階段、二階段提交和回滾均由 Seata 框架自動生成,用戶只需編寫“業務 SQL”,便能輕松接入分布式事務,AT 模式是一種對業務無任何侵入的分布式事務解決方案。
    • 一階段:
      • 在一階段,Seata 會攔截“業務 SQL”,首先解析 SQL 語義,找到“業務 SQL”要更新的業務數據,在業務數據被更新前,將其保存成before image,然后執行“業務 SQL”更新業務數據,在業務數據更新之后,再將其保存成after image,最后生成行鎖。
      • 以上操作全部都在一個數據庫事務內完成,這樣保證了一階段操作的原子性。
        一階段
    • 二階段提交:
      • 二階段如果是提交的話,因為“業務 SQL”在一階段已經提交至數據庫, 所以 Seata 框架只需將一階段保存的快照數據和行鎖刪掉,完成數據清理即可。
        二階段提交
    • 二階段回滾:
      • 二階段如果是回滾的話,Seata 就需要回滾一階段已經執行的“業務 SQL”,還原業務數據。回滾方式便是用“before image”還原業務數據;但在還原前要首先要校驗臟寫,對比“數據庫當前業務數據”和 “after image”,如果兩份數據完全一致就說明沒有臟寫,可以還原業務數據,如果不一致就說明有臟寫,出現臟寫就需要轉人工處理。
        二階段回滾

3.2 TCC 模式

  • 侵入性比較強, 并且需要自己實現相關事務控制邏輯;
  • 在整個過程基本沒有鎖,性能更強;
  • TCC 模式需要用戶根據自己的業務場景實現 TryConfirmCancel 三個操作;
    • 事務發起方在一階段執行 Try 方法,
    • 在二階段提交執行 Confirm 方法,二階段回滾執行 Cancel 方法。
  • TCC 三個方法描述:
    • Try:資源的檢測和預留;
    • Confirm:執行的業務操作提交,要求 Try 成功 Confirm 一定要能成功;
    • Cancel:預留資源的釋放;
      TCC模式
  • TCC的實踐經驗:
    • 螞蟻金服TCC實踐,總結以下注意事項:
      • 業務模型分2階段設計
      • 并發控制
      • 允許空回滾
      • 防懸掛控制
      • 冪等控制
    • 1、TCC 設計 – 業務模型分 2 階段設計:
      • 用戶接入 TCC 模式,最重要的事情就是考慮如何將業務模型拆成 2 階段,實現成 TCC 的 3 個方法,并且保證 Try 成功 Confirm 一定能成功。相對于 AT 模式,TCC 模式對業務代碼有一定的侵入性,但是 TCC 模式無 AT 模式的全局行鎖,TCC 性能會比 AT 模式高很多。
      • 以“扣錢”場景為例,在接入 TCC 前,對 A 賬戶扣錢,只需一條更新賬戶余額的 SQL 便能完成;但是在接入 TCC 之后,用戶就需要考慮如何將原來一步就能完成的扣錢操作,拆成兩階段,實現成三個方法,并且保證一階段 Try 成功的話 二階段 Confirm 一定能成功。
        示例
      • 如上圖所示,Try 方法作為一階段的準備方法,需要做資源的檢查和預留。在扣錢場景下,Try 要做的事情是就是檢查賬戶余額是否充足,預留轉賬資金,預留的方式就是凍結 A 賬戶的 轉賬資金。Try 方法執行之后,賬號 A 余額雖然還是 100,但是其中 30 元已經被凍結了,不能被其他事務使用。
      • 二階段 Confirm 方法執行真正的扣錢操作。Confirm 會使用 Try 階段凍結的資金,執行賬號扣款。Confirm 方法執行之后,賬號 A 在一階段中凍結的 30 元已經被扣除,賬號 A 余額變成 70 元 。
      • 如果二階段是回滾的話,就需要在 Cancel 方法內釋放一階段 Try 凍結的 30 元,使賬號 A 的回到初始狀態,100 元全部可用。
    • 2、TCC 設計 – 允許空回滾:
      允許空回滾
      • Cancel 接口設計時需要允許空回滾。在 Try 接口因為丟包時沒有收到,事務管理器會觸發回滾,這時會觸發 Cancel 接口,這時 Cancel 執行時發現沒有對應的事務 xid 或主鍵時,需要返回回滾成功。讓事務服務管理器認為已回滾,否則會不斷重試,而 Cancel 又沒有對應的業務數據可以進行回滾。
    • 3、TCC 設計 – 防懸掛控制:
      防懸掛控制
      • 懸掛的意思是:Cancel 比 Try 接口先執行,出現的原因是 Try 由于網絡擁堵而超時,事務管理器生成回滾,觸發 Cancel 接口,而最終又收到了 Try 接口調用,但是 Cancel 比 Try 先到。按照前面允許空回滾的邏輯,回滾會返回成功,事務管理器認為事務已回滾成功,則此時的 Try 接口不應該執行,否則會產生數據不一致,所以我們在 Cancel 空回滾返回成功之前先記錄該條事務 xid 或業務主鍵,標識這條記錄已經回滾過,Try 接口先檢查這條事務xid或業務主鍵如果已經標記為回滾成功過,則不執行 Try 的業務操作。
    • 4、TCC 設計 – 冪等控制:
      冪等控制
      • 冪等性的意思是:對同一個系統,使用同樣的條件,一次請求和重復的多次請求對系統資源的影響是一致的。因為網絡抖動或擁堵可能會超時,事務管理器會對資源進行重試操作,所以很可能一個業務操作會被重復調用,為了不因為重復調用而多次占用資源,需要對服務設計時進行冪等控制,通常我們可以用事務 xid 或業務主鍵判重來控制。

3.3 Saga模式

  • Saga 理論出自 Hector & Kenneth 1987發表的論文 Sagas。
  • Saga模式的實現,是長事務解決方案。
    Saga模式
  • Saga 是一種補償協議,在 Saga 模式下,分布式事務內有多個參與者,每一個參與者都是一個沖正補償服務,需要用戶根據業務場景實現其正向操作和逆向回滾操作。
    • 分布式事務執行過程中,依次執行各參與者的正向操作,如果所有正向操作均執行成功,那么分布式事務提交。如果任何一個正向操作執行失敗,那么分布式事務會退回去執行前面各參與者的逆向回滾操作,回滾已提交的參與者,使分布式事務回到初始狀態。
    • Saga 正向服務與補償服務也需要業務開發者實現。因此是業務入侵的。
    • Saga 模式下分布式事務通常是由事件驅動的,各個參與者之間是異步執行的,Saga 模式是一種長事務解決方案。
      沖正
  • Saga 模式使用場景:
    • Saga 模式適用于業務流程長且需要保證事務最終一致性的業務系統,Saga 模式一階段就會提交本地事務,無鎖、長流程情況下可以保證性能。
    • 事務參與者可能是其它公司的服務或者是遺留系統的服務,無法進行改造和提供 TCC 要求的接口,可以使用 Saga 模式。
  • Saga模式的優勢是:
    • 一階段提交本地數據庫事務,無鎖,高性能;
    • 參與者可以采用事務驅動異步執行,高吞吐;
    • 補償服務即正向服務的“反向”,易于理解,易于實現;

3.4 XA模式

  • XA是X/Open DTP組織(X/Open DTP group)定義的兩階段提交協議,XA被許多數據庫(如Oracle、DB2、SQL Server、MySQL)和中間件等工具(如CICS 和 Tuxedo)本地支持 。
  • X/Open DTP模型(1994)包括應用程序(AP)、事務管理器(TM)、資源管理器(RM)。
  • XA接口函數由數據庫廠商提供。XA規范的基礎是兩階段提交協議2PC。
  • JTA(Java Transaction API) 是Java實現的XA規范的增強版 接口。
  • 在XA模式下,需要有一個[全局]協調器,每一個數據庫事務完成后,進行第一階段預提交,并通知協調器,把結果給協調器。協調器等所有分支事務操作完成、都預提交后,進行第二步;
  • 第二步:協調器通知每個數據庫進行逐個commit/rollback。
  • 其中,這個全局協調器就是XA模型中的TM角色,每個分支事務各自的數據庫就是RM。
    MySQL 提供的XA實現(https://dev.mysql.com/doc/refman/5.7/en/xa.html )
  • XA模式下的 開源框架有atomikos,其開發公司也有商業版本。
  • XA模式缺點:事務粒度大。高并發下,系統可用性低。因此很少使用。

3.5 (AT、TCC、Saga、XA)模式分析

  • 四種分布式事務模式,分別在不同的時間被提出,每種模式都有它的適用場景。
    • AT 模式是無侵入的分布式事務解決方案,適用于不希望對業務進行改造的場景,幾乎0學習成本。
    • TCC 模式是高性能分布式事務解決方案,適用于核心系統等對性能有很高要求的場景。
    • Saga 模式是長事務解決方案,適用于業務流程長且需要保證事務最終一致性的業務系統,Saga 模式一階段就會提交本地事務,無鎖,長流程情況下可以保證性能,多用于渠道層、集成層業務系統。事務參與者可能是其它公司的服務或者是遺留系統的服務,無法進行改造和提供 TCC 要求的接口,也可以使用 Saga 模式。
    • XA模式是分布式強一致性的解決方案,但性能低而使用較少。
  • 分布式事務本身就是一個技術難題,業務中具體使用哪種方案還是需要不同的業務特點自行選擇,但是我們也會發現,分布式事務會大大的提高流程的復雜度,會帶來很多額外的開銷工作,「代碼量上去了,業務復雜了,性能下跌了」。所以,當我們真實開發的過程中,能不使用分布式事務就不使用。

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/web/45337.shtml
繁體地址,請注明出處:http://hk.pswp.cn/web/45337.shtml
英文地址,請注明出處:http://en.pswp.cn/web/45337.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

J025_斗地主游戲案例開發(簡版)

一、需求描述 完成斗地主游戲的案例開發。 業務:總共有54張牌; 點數:3、4、5、6、7、8、9、10、J、Q、K、A、2 花色:黑桃、紅桃、方片、梅花 大小王:大王、小王 點數分別要組合4種花色,大小王各一張。…

[激光原理與應用-114]:南京科耐激光-激光焊接-焊中檢測-智能制程監測系統IPM介紹 - 18 - 產品宣傳、介紹、產品價值、幫助客戶解決的問題

目錄 一、第一印象 1.1 我是誰?產品是什么?產品在產業鏈中的位置 1.2 公司在產業鏈中的位置?公司簡介? 二、IPM工作原理 2.1 IPM系統組成 2.2 基于激光熔池光學檢測原理 2.3 基于信號特征的檢測原理 三、IPM產品如何與客…

2-17,18,19 -- 關于指針

指針(pointer 聲明指針 int *p;定義指針 int a 4; int *p &a; //指針p是指向變量a的地址的指針指針數組 int *arr[5];數組指針 int (*arr)[5];函數指針 int (*fun)(int,int) // 聲明一個指向函數的指針,這個函數的返回值是int,有兩個int的參數指針的指針 int **p;…

ArkTS學習筆記_封裝復用之@Styles裝飾器

ArkTS學習筆記_封裝復用之Styles裝飾器 背景: 在開發中,如果每個組件的樣式都需要單獨設置,就會出現大量代碼在進行重復樣式設置,雖然可以復制粘貼,但為了代碼簡潔性和后續方便維護,給出的思路是&#xff…

jmeter分布式(四)

一、gui jmeter的gui主要用來調試腳本 1、先gui創建腳本 先做一個腳本 演示:如何做混合場景的腳本? 用211的業務比例 ①啟動數據庫服務 數據庫服務:包括mysql、redis mysql端口默認3306 netstat -lntp | grep 3306處于監聽狀態&#xf…

深入了解MySQL中的innodb_lock_wait_timeout

引言 在數據庫管理中,確保數據的一致性和完整性是至關重要的。MySQL的InnoDB存儲引擎通過行級鎖定機制來實現這一點。然而,當多個事務同時操作數據庫時,可能會出現鎖等待的情況。了解并合理配置innodb_lock_wait_timeout參數,對于…

數據庫第6次作業

內容 1、創建視圖v_emp_dept_id_1,查詢銷售部門的員工姓名和家庭住址 2、創建視圖v_emp_dept,查詢銷售部門員工姓名和家庭住址及部門名稱。 3、創建視圖v_dept_emp_count(dept_name,emp_count,avg_salay),統計每個部門人數并計算平均工資。 …

Spring 使用log4j

porn.xml 引入依賴 <dependency><groupId>org.apache.logging.log4j</groupId><artifactId>log4j-core</artifactId><version>2.23.1</version></dependency><dependency><groupId>org.apache.logging.log4j<…

解讀網傳《深圳IT圈?新解讀八小時工作制》

網傳深圳IT圈的新解讀八小時工作制 工作時間安排&#xff1a; 10:00-12:0014:00-18:0019:00-21:00 初看&#xff1a;有驚喜 上午開始時間晚&#xff1a;相對于傳統的9點開始&#xff0c;這種安排允許員工有更多的早晨時間&#xff0c;可以用來休息或處理個人事務。下午和晚上分…

typescript新規范及vue3常用的屬性解析【2024】

文章目錄 如在vue中 使用tyescript來規范定義類型解釋一下 < >的意思 定義 了 personList &#xff1a;是個數組 Array 且要告訴里面每一項 結構長什么樣 Array<PersonInter>definepropsvue3中的hooks組件父子組件 方法、數據、相互調用 如在vue中 使用tyescript來…

【LSTM和GRU極簡,和最新的TT也就是狀態】機器學習模型來學習狀態

LSTM&#xff08;長短期記憶網絡&#xff09;中的關鍵參數包括輸入門、遺忘門、輸出門、細胞狀態和隱藏狀態。以下是如何進行推理計算的示例&#xff1a; LSTM參數和公式 輸入門&#xff08;i_t&#xff09;&#xff1a;決定輸入的信息量。 遺忘門&#xff08;f_t&#xff0…

【React Native】做了一個簡約的雷達圖組件

本文目錄 【React Native】做了一個簡約的雷達圖組件獲取組件實現思路用法示例簡易用法自定義美化 結語 【React Native】做了一個簡約的雷達圖組件 最近在使用 react-native 中需要繪制雷達圖&#xff0c;沒有找到合適的小組件&#xff08;大的圖表庫未直接提供&#xff0c;需…

pico+unity3d運行測試方法

一. 發布并運行程序 這個就很簡單&#xff0c;電腦和pico數據庫連接、pico打開開發者模式、運行的時候選擇設備pico 二. pico串流助手 1.需要先下載pico的軟件 PICO Developer Center、并安裝串流助手、這種方式的話&#xff0c;安裝了向日葵的小伙伴可能有沖突、百度一下解…

c#中的特性

在C#中&#xff0c;特性&#xff08;Attributes&#xff09;是一種向程序元素&#xff08;如類、方法、屬性等&#xff09;添加元數據的方式。特性可以用來提供關于程序元素的附加信息&#xff0c;這些信息可以在編譯時和運行時被訪問。 特性主要有以下幾個用途&#xff1a; 提…

手機數據恢復篇:如何從 Android 設備內恢復數據

如何從 Android 內部存儲恢復數據&#xff1f; 要從 Android 內部存儲恢復已刪除的文件&#xff0c;您需要一個 Android 內部存儲恢復應用或程序。請繼續閱讀以獲取可靠的 Android 數據恢復軟件&#xff0c;并讓它幫助您從 Android 手機的內部存儲恢復數據。 是否有可能恢復 An…

Typescript 合并接口

在TypeScript中&#xff0c;合并接口&#xff08;Interface Merging&#xff09;是一種強大的特性&#xff0c;它允許你擴展現有的接口&#xff0c;無論是通過聲明合并還是在同一個聲明塊中直接擴展。這種特性在基于類的面向對象編程中非常有用&#xff0c;但TypeScript的接口合…

4-2 權重衰減

前一節我們描述了過擬合的問題&#xff0c;本節我們將介紹一些正則化模型的技術。 我們總是可以通過去收集更多的訓練數據來緩解過擬合。 但這可能成本很高&#xff0c;耗時頗多&#xff0c;或者完全超出我們的控制&#xff0c;因而在短期內不可能做到。 假設我們已經擁有盡可能…

圖片轉文字的軟件,分享3種不同的類型的軟件!

在信息爆炸的時代&#xff0c;圖片作為一種直觀、生動的信息載體&#xff0c;已經成為我們日常生活中不可或缺的一部分。然而&#xff0c;有時候我們可能需要將圖片中的文字提取出來&#xff0c;以便于編輯、整理或進一步使用。那么&#xff0c;有哪些實用的圖片轉文字軟件可以…

2718. 查詢后矩陣的和

題目描述&#xff1a; 給你一個整數 n 和一個下標從 0 開始的 二維數組 queries &#xff0c;其中 queries[i] [typei, indexi, vali] 。 一開始&#xff0c;給你一個下標從 0 開始的 n x n 矩陣&#xff0c;所有元素均為 0 。每一個查詢&#xff0c;你需要執行以下操作之一…

Java-數據結構基礎

棧結構 : 先進后出 隊列結構 : 先進先出 數組結構 : 查詢快 , 增刪慢 鏈表結構 : 查詢慢 , 增刪快 二叉樹 二叉樹 : 每個節點最多有兩個子節點 二茬查找樹 : 每個節點的左子節點比當前節點小 , 右子節點比當前節點大 二茬平衡樹 : 在查找樹的基礎上, 每個節點左右子樹的高…