索引葉節點中的條目是如何排序的？
我正在閱讀“SQL 性能解釋”一書，在談到索引時，它說數據庫使用雙向鍊錶來連接索引葉節點。每個節點都儲存在一個數據庫塊中，由不同的索引條目組成。
然後它說索引順序維護在兩個級別：一個在每個葉節點內，以及在不同的葉節點本身內（通過鍊錶），如下圖左側所示。
我的問題是：我了解對塊使用雙向鍊錶的優點，以便在插入新塊時更容易維護順序（這是圍繞一些指針移動的問題）。但是，在塊本身內，如果保持順序，那麼性能如何？假設一個塊中有很多條目，如果要在塊中插入一個新條目，那不是真的很糟糕（因為沒有諸如雙向鍊錶之類的資料結構）。
您提出的性能問題比有關其工作原理的理論所能回答的要實用一些。（我確信有一個大 O 表示法的答案來概括性能，但我不知道它是不是在我的腦海中。）
在實踐中，大多數數據庫系統都有不同的配置選項來決定何時拆分葉級節點的塊。例如，在 Microsoft SQL Server 中，這稱為Fill Factor。填充因子確定在初始創建（或索引的下一次重建）時應該用數據填充葉級塊的填充量（或者為將來的數據插入留下多少可用空間）以調整拆分操作應該發生的頻率。
先前連結的文章詳細介紹了此內容，但簡而言之，這可以配置為 1% 到 100% 之間的任何位置（在 SQL Server 中，0% 是 100% 的假象），這意味著“將 99% 的塊留空以供將來插入”到“完全填滿方塊”，以及介於兩者之間的任何地方。這個設置會以各種方式影響性能，但是當一個塊被填滿時不可避免地會發生一個塊拆分事件，這有點繁重的操作。
但是有一些補償，例如在 Microsoft SQL Server 中，在此拆分事件期間會發生少量索引碎片。這允許在數據的物理排序可能與 B 樹中的邏輯排序不完全匹配的權衡下更快地發生拆分。從理論上講，這會影響使用該索引的 SELECT 查詢的最後一步的性能，當葉節點查找其數據所在的數據頁時。雖然這種性能在現實世界中非常微不足道，並且隨著時間的推移，如果有足夠的索引碎片發生有一些方法可以修復它，例如重建或重組索引。
總而言之，是的，當塊需要拆分時，性能會受到少量影響，但是現代數據庫系統有不同的方法來控制這種情況發生的頻率，例如 MS SQL Server 中的填充因子設置，它們減少了對性能的影響允許在稍後對索引進行查詢的可忽略權衡的情況下進行碎片化。它們還提供了通過索引重建或重組來修復碎片的方法來補償這些優化的權衡。