天天看點

紅黑樹-概述

hash不支援範圍

hash不排序

hash不支援模糊排序

hash碰撞

hash模糊

資料庫為什麼使用B+樹而不是B樹

  • B樹隻适合随機檢索,而B+樹同時支援随機檢索和順序檢索;
  • B+樹空間使用率更高,可減少I/O次數,磁盤讀寫代價更低。一般來說,索引本身也很大,不可能全部存儲在記憶體中,是以索引往往以索引檔案的形式存儲的磁盤上。這樣的話,索引查找過程中就要産生磁盤I/O消耗。B+樹的内部結點并沒有指向關鍵字具體資訊的指針,隻是作為索引使用,其内部結點比B樹小,盤塊能容納的結點中關鍵字數量更多,一次性讀入記憶體中可以查找的關鍵字也就越多,相對的,IO讀寫次數也就降低了。而IO讀寫次數是影響索引檢索效率的最大因素;
  • B+樹的查詢效率更加穩定。B樹搜尋有可能會在非葉子結點結束,越靠近根節點的記錄查找時間越短,隻要找到關鍵字即可确定記錄的存在,其性能等價于在關鍵字全集内做一次二分查找。而在B+樹中,順序檢索比較明顯,随機檢索時,任何關鍵字的查找都必須走一條從根節點到葉節點的路,所有關鍵字的查找路徑長度相同,導緻每一個關鍵字的查詢效率相當。
  • B-樹在提高了磁盤IO性能的同時并沒有解決元素周遊的效率低下的問題。B+樹的葉子節點使用指針順序連接配接在一起,隻要周遊葉子節點就可以實作整棵樹的周遊。而且在資料庫中基于範圍的查詢是非常頻繁的,而B樹不支援這樣的操作。
  • 增删檔案(節點)時,效率更高。因為B+樹的葉子節點包含所有關鍵字,并以有序的連結清單結構存儲,這樣可很好提高增删效率。

CountDownLatch的計數器隻能使用一次。而CyclicBarrier的計數器可以使用reset()

方法重置。是以CyclicBarrier能處理更為複雜的業務場景,比如如果計算發生錯誤,可以重置計數器,并讓線程們重新執行一次。

CyclicBarrier還提供其他有用的方法,比如getNumberWaiting方法可以獲得CyclicBarrier阻塞的線程數量。isBroken方法用來知道阻塞的線程是否被中斷。比如以下代碼執行完之後會傳回true。

CountDownLatch會阻塞主線程,CyclicBarrier不會阻塞主線程,隻會阻塞子線程。

某線程中斷CyclicBarrier會抛出異常,避免了所有線程無限等待。

紅黑樹

根節點永遠是黑色

紅色結點的葉子節點都是黑色

所有的葉子結點位元組點都是黑色

隻有紅色或者黑色

從任意一個節點的字數到每個葉子的路徑都含有相同的黑色節點

紅黑樹與AVL樹,各自的優缺點總結

  1. 紅黑樹不追求"完全平衡",即不像AVL那樣要求節點的​

    ​|balFact| <= 1​

    ​,它隻要求部分達到平衡,但是提出了為節點增加顔色,紅黑是用非嚴格的平衡來換取增删節點時候旋轉次數的降低,任何不平衡都會在三次旋轉之内解決,而AVL是嚴格平衡樹,是以在增加或者删除節點的時候,根據不同情況,旋轉的次數比紅黑樹要多。
  2. 就插入節點導緻樹失衡的情況,AVL和RB-Tree都是最多兩次樹旋轉來實作複衡rebalance,旋轉的量級是O(1)

    删除節點導緻失衡,AVL需要維護從被删除節點到根節點root這條路徑上所有節點的平衡,旋轉的量級為O(logN),而RB-Tree最多隻需要旋轉3次實作複衡

    隻需O(1),是以說RB-Tree删除節點的rebalance的效率更高,開銷更小!

  3. AVL的結構相較于RB-Tree更為平衡,插入和删除引起失衡,如2所述,RB-Tree複衡效率更高;當然,由于AVL高度平衡,是以AVL的Search效率更高啦。
  4. 針對插入和删除節點導緻失衡後的rebalance操作,紅黑樹能夠提供一個比較"便宜"的解決方案,降低開銷,是對search,insert ,以及delete效率的折衷,總體來說,RB-Tree的統計性能高于AVL.
  5. 故引入RB-Tree是功能、性能、空間開銷的折中結果
紅黑樹-概述

靜态代理和動态代理差別

今天看了下資料。大緻清楚靜态代理和動态代理的差別

代理模式有兩種:1.靜态代理 2.動态代理

個人了解最主要的卻别:

靜态代理:是在java檔案編譯前,手動寫好代理類對象。這樣隻能代理一類對象,即一類接口的類型。

動态代理:是通過反射原理,在程式運作的時候動态的生成的代理對象,是以可以代理任意的類對象。

紅黑樹-概述

redo log 是 InnoDB 引擎特有的;binlog 是 MySQL 的 Server 層實作的,所有引擎共用。

redo log 是實體日志,記錄的是“在某個資料頁上做了什麼修改”;binlog 是邏輯日志,記錄的是這個語句的原始邏輯,比如“給 ID=1 這一行的 c 字段加 1 ”。

redo log 是循環寫的,空間固定會用完然後複寫;binlog 是可以追加寫入的。“追加寫”是指 binlog 檔案寫到一定大小後會切換到下一個,并不會覆寫以前的日志。

對MySQL來說,邏輯備份日志(binlog)、重做日志(redolog)、復原日志(undolog)、鎖技術 + MVCC就是MySQL實作事務的基礎。

原子性:通過undolog來實作。

持久性:通過binlog、redolog來實作。

隔離性:通過(讀寫鎖+MVCC)來實作。

一緻性:MySQL通過原子性,持久性,隔離性最終實作(或者說定義)資料一緻性。

CMS收集器和G1收集器,優缺點對比