索引的首要目的，是提供被索引資料的有序表示。但資料無法直接依序連續存放——否則每次 insert 都得把後面的條目全部往後搬，而搬動大量資料極為耗時，插入將慢到不可接受。

解法是：建立一個與記憶體實體順序無關的邏輯順序。

雙向鏈結串列建立邏輯順序#

這個邏輯順序透過雙向鏈結串列（doubly linked list）達成：

• 每個節點都持有指向前後兩個相鄰條目的連結，像一條鏈子。
• 新節點插入兩個既有節點之間時，只需更新它們的連結指向新節點；新節點的實體位置無關緊要，邏輯順序由串列本身維持。
• 之所以叫「雙向」，是因為每個節點同時指向前一個與後一個節點——這讓資料庫能向前或向後讀取索引。

這個設計的意義在於：插入新條目時不需搬動大量資料，只要改幾個指標。

雙向鏈結串列在許多程式語言中也用於實作集合容器：

葉節點與區塊：兩個層級的順序#

資料庫用雙向鏈結串列串起所謂的索引葉節點（index leaf node）：

• 每個葉節點存放在一個資料庫區塊（block）或頁（page）中，也就是資料庫最小的儲存單位。
• 所有索引區塊大小相同——通常是幾 KB。資料庫會盡可能用滿每個區塊，塞進越多索引條目越好。

因此索引順序其實維持在兩個不同層級上：

1. 每個葉節點內部的索引條目順序。
2. 葉節點彼此之間的順序，由雙向鏈結串列維持。

索引有序，資料表無序#

每個索引條目由被索引的欄位（鍵值）加上一個指向對應資料列的參照（Oracle 稱 ROWID，SQL Server 稱 RID）組成。

與索引不同，資料表的資料存放在堆積（heap）結構中，完全未排序。同一個資料表區塊內的各列之間沒有任何關聯，區塊與區塊之間也沒有連結。

這個「索引有序、資料表無序」的落差，正是後續章節討論效能問題的根源。