# Итераторы коллекций armdb
## Обзор
Упорядоченная итерация **всегда** доступна для **Tree**-коллекций (индекс SkipList):
ConstTree, VarTree, TypedTree, ZeroTree.
**Map**-коллекции могут подключить итерацию через `Config::iterable(true)` (или
`FixedConfig::iterable(true)`), что создаёт per-shard companion key index (`BTreeSet`).
Локальные вызовы для Map используют `iter_view()`; RPC-вызовы — `First`/`Last`/`Range`/`RangeKeys`.
Map-сканы предназначены для редких административных и maintenance-задач. Они **weakly consistent**:
шардовые блокировки снимаются между батчами, поэтому конкурентные записи могут быть видны
частично. Tree-сканы тоже weakly consistent и **не** являются point-in-time snapshot.
| `iter()` / `iter_view().iter()` | Все записи | полный обход |
| `range(start, end)` | Диапазон `[start, end)` | включая start, исключая end |
| `range_bounds(start, end)` | Диапазон с произвольными `Bound` | `Included`, `Excluded`, `Unbounded` |
| `prefix_iter(prefix)` | Ключи с заданным префиксом | автоматические границы |
Tree-итераторы реализуют `Iterator` + `DoubleEndedIterator`. Map-итераторы через
`iter_view()` — только `Iterator` (однонаправленный обход по шардам).
---
## Типы итераторов
| ConstTree | `ConstIter<'a, K, V>` | `(K, [u8; V])` — копия | нет |
| VarTree | `VarIter<'a, K, H>` | `(K, ByteView)` — RC | возможен (cache miss) |
| TypedTree | `TypedIter<'a, K, T>` | `(K, &'a T)` — ссылка | нет |
| ZeroTree | `ZeroIter<'a, K, V, T>` | `(K, T)` — копия | нет |
| TypedMap | `TypedMapIterView` → `TypedMapIter` | `(K, TypedRef<'a, T>)` — guard | нет |
| ZeroMap | `ZeroMapIterView` → `iter()` | `(K, T)` — копия | нет |
| VarTypedMap | `VarTypedMapIterView` → `VarTypedMapIter` | `(K, T)` — decode | возможен (cache miss) |
Операции только по ключам (`keys()`, `keys_range()`, `keys_prefix()` и RPC `RangeKeys`)
обходят companion `BTreeSet` без материализации значений.
### Возврат значений
- **ConstTree** — `[u8; V]` копируется из inline SeqLock (`node.read_value()`)
- **VarTree** — `ByteView` читается через `read_value_cached(&disk)`, при промахе block cache — pread с диска
- **TypedTree** — `&'a T` ссылка на значение в `TypedData`, защищённая seize guard
- **ZeroTree** — обёртка над `ConstIter`, `[u8; V]` → `T` через zerocopy (`from_value_bytes`)
- **TypedMap** — `TypedRef<'a, T>` под seize guard; `iter_view()` возвращает `None` без `iterable(true)`
- **ZeroMap** — `T` копируется из inline `[u8; V]` через zerocopy
- **VarTypedMap** — `T` декодируется из `ByteView` при каждом шаге; при промахе block cache — pread
---
## Структура итератора
Все итераторы (кроме ZeroIter) имеют одинаковую структуру:
```rust,ignore
pub struct ConstIter<'a, K: Key, const V: usize> {
list: &'a SkipList<ConstNode<K, V>>,
front: *mut ConstNode<K, V>, // указатель вперёд
back: *mut ConstNode<K, V>, // указатель назад
end: Bound<K>, // верхняя граница (forward)
start: Bound<K>, // нижняя граница (backward)
reversed: bool, // флаг обратного порядка
done: bool, // front == back — итерация завершена
_guard: seize::LocalGuard<'a>, // предотвращает reclamation нод
}
```
`ZeroIter` — тонкая обёртка:
```rust,ignore
pub struct ZeroIter<'a, K: Key, const V: usize, T> {
inner: ConstIter<'a, K, V>,
_marker: PhantomData<T>,
}
```
`VarIter` отличается тем, что хранит `tree: &'a VarTree<K, H>` вместо `list`,
чтобы читать значения через block cache.
---
## Алгоритм обхода
### next() — прямой обход
```text
loop:
converged = (front == back)
front = node.tower[0].next() // двигаем front вперёд
if converged → done = true
if node.is_marked() → skip // удалённая нода
if !check_end(node.key) → None // вышли за границу
return Some((key, value))
```
### next_back() — обратный обход
```text
loop:
converged = (front == back)
back = list.find_last_lt(key) // двигаем back назад
if converged → done = true
if node.is_marked() → skip
if !check_start(node.key) → None
return Some((key, value))
```
Асимметрия: `next()` использует `tower[0].next()` (O(1)), а `next_back()` — `find_last_lt()` (O(log n)).
### Конвергенция
Когда `front == back`, итератор устанавливает `done = true`. После этого и `next()`, и `next_back()` возвращают `None`. Это предотвращает повторную выдачу элемента.
---
## Reversed ordering
По умолчанию `Config::reversed = true` — SkipList хранит ключи в обратном порядке (компаратор `b.cmp(a)`).
| true (default) | descending | ascending |
| false | ascending | descending |
Проверка границ учитывает `reversed`:
```rust,ignore
// check_end (forward direction)
fn check_end(&self, key: &K) -> bool {
match &self.end {
Bound::Unbounded => true,
Bound::Excluded(end) => {
if self.reversed { key > end } else { key < end }
}
Bound::Included(end) => {
if self.reversed { key >= end } else { key <= end }
}
}
}
```
---
## Prefix search
`prefix_iter(prefix)` вычисляет границы через `prefix_bounds()`:
**reversed = false:**
- `search_key` = prefix + `0x00` padding → первый ключ с этим префиксом
- `end` = `prefix + 1` (инкремент последнего байта) как `Excluded` bound; если overflow (все `0xFF`) — `Unbounded`
**reversed = true:**
- `search_key` = prefix + `0xFF` padding → последний ключ с этим префиксом
- `end` = prefix + `0x00` padding как `Included` bound
```rust
// Пример: prefix = [0x01]
// reversed=true:
// search = [0x01, 0xFF, 0xFF, ...] — ищем от конца группы
// end = [0x01, 0x00, 0x00, ...] — до начала группы (Included)
// reversed=false:
// search = [0x01, 0x00, 0x00, ...] — ищем от начала группы
// end = [0x02, 0x00, 0x00, ...] — до следующей группы (Excluded)
```
---
## Weakly-consistent семантика
Итераторы **не** создают point-in-time snapshot. Они являются weakly-consistent:
- Конкурентные вставки/обновления **могут быть видны** во время итерации
- Удалённые записи (marked nodes в Tree; CAS-удаления в Map) автоматически **пропускаются**
- `seize::LocalGuard` предотвращает reclamation памяти нод на время жизни Tree-итератора
- Map-итераторы снимают shard lock между батчами — снимок коллекции не гарантируется
---
## VarTree: disk I/O при итерации
`VarIter` — единственный итератор, который может выполнять disk I/O:
```rust,ignore
fn next(&mut self) -> Option<Self::Item> {
// ... обход SkipList ...
let disk = *node.load_disk();
match self.tree.read_value_cached(&disk) {
Some(value) => return Some((node.key, value)),
None => continue, // значение недоступно (compacted), пропускаем
}
}
```
При промахе block cache выполняется `pread` с диска. Для предзагрузки кэша используйте `warmup()`.
---
## Helper-методы
| ConstIter | `collect_vec()` | `Vec<(K, [u8; V])>` |
| TypedIter | `collect_vec()` | `Vec<(K, &T)>` |
| VarIter | `collect_keys()` | `Vec<K>` — только ключи |
| VarIter | `collect_entries()` | `Vec<(K, ByteView)>` |
---
## Send safety
Все итераторы содержат raw pointers и реализуют `unsafe impl Send`:
```rust,ignore
// SAFETY: итератор держит seize guard, который предотвращает
// reclamation нод. Raw pointer разыменовывается только пока guard жив.
unsafe impl<K: Key, const V: usize> Send for ConstIter<'_, K, V> {}
unsafe impl<K: Key, H: WriteHook<K>> Send for VarIter<'_, K, H> {}
unsafe impl<K: Key, T: Send + Sync> Send for TypedIter<'_, K, T> {}
```
ZeroIter наследует Send от ConstIter (обёртка).
---
## Стоимость операций
| `next()` | O(1), zero I/O | O(1) + возможен pread | O(1), zero I/O | O(1), zero I/O |
| `next_back()` | O(log n), zero I/O | O(log n) + возможен pread | O(log n), zero I/O | O(log n), zero I/O |
| `prefix_iter()` setup | O(log n) | O(log n) | O(log n) | O(log n) |
| `range()` setup | O(log n) | O(log n) | O(log n) | O(log n) |
---
## Примеры использования
### Полный обход
```rust,ignore
// ConstTree
for (key, value) in tree.iter() {
// key: [u8; K], value: [u8; V]
}
// TypedTree
for (key, user) in tree.iter() {
// key: [u8; K], user: &User
}
// ZeroTree
for (key, counters) in tree.iter() {
// key: [u8; K], counters: Counters (Copy)
}
```
### Prefix search — "последние N записей"
```rust,ignore
// Составной ключ: [user_id:8][post_id:8]
// reversed=true (default) → prefix_iter возвращает от новых к старым
let latest_posts: Vec<_> = tree
.prefix_iter(&user_id)
.take(20)
.collect();
```
### Range query
```rust,ignore
// Диапазон [start, end) — start включительно, end исключительно
let start = 5u64.to_be_bytes();
let end = 10u64.to_be_bytes();
for (key, value) in tree.range(&start, &end) {
// reversed=true → ключи 9, 8, 7, 6, 5
}
```
### range_bounds — произвольные границы
`range_bounds(start: Bound<&K>, end: Bound<&K>)` — обобщение `range()`.
Каждая граница может быть `Included`, `Excluded` или `Unbounded`.
`range(start, end)` эквивалентен `range_bounds(Bound::Included(start), Bound::Excluded(end))`.
```rust,ignore
use std::ops::Bound;
// (5, 10] — исключить 5, включить 10
let entries: Vec<_> = tree.range_bounds(
Bound::Excluded(&5u64.to_be_bytes()),
Bound::Included(&10u64.to_be_bytes()),
).collect();
// reversed=true → 10, 9, 8, 7, 6
// [5, 10] — включить обе границы
let entries: Vec<_> = tree.range_bounds(
Bound::Included(&5u64.to_be_bytes()),
Bound::Included(&10u64.to_be_bytes()),
).collect();
// reversed=true → 10, 9, 8, 7, 6, 5
// (5, ..) — от 5 исключительно до конца
let entries: Vec<_> = tree.range_bounds(
Bound::Excluded(&5u64.to_be_bytes()),
Bound::Unbounded,
).collect();
// (.., 10) — от начала до 10 исключительно
let entries: Vec<_> = tree.range_bounds(
Bound::Unbounded,
Bound::Excluded(&10u64.to_be_bytes()),
).collect();
```
### DoubleEndedIterator
```rust,ignore
// .rev() — обратный порядок
let oldest: Vec<_> = tree.prefix_iter(&user_id).rev().take(10).collect();
// Смешанный обход: next() + next_back()
let mut iter = tree.iter();
let first = iter.next(); // первый в порядке итерации
let last = iter.next_back(); // последний в порядке итерации
// Итератор схлопывается к центру
```
### VarTree — предзагрузка кэша
```rust,ignore
// Предзагрузить все значения в block cache перед итерацией
tree.warmup()?;
for (key, value) in tree.iter() {
// value: ByteView — без disk I/O после warmup
}
```