Побитовая попытка с растровым изображением
Побитовое дерево — это особая форма дерева , в которой каждый узел с его дочерними ветвями представляет собой битовую последовательность одного или нескольких битов ключа. Побитовое дерево с растровым изображением использует растровое изображение для обозначения допустимых дочерних ветвей.
Попытки и побитовые попытки
[ редактировать ]Дерево — это тип дерева поиска , в котором — в отличие, например, от B-дерева — ключи хранятся не в узлах, а на пути к листьям. Ключ распределен по древовидной структуре. В «классическом» дереве каждый узел с его дочерними ветвями представляет один символ алфавита одной позиции (символа) ключа.
В побитовых попытках ключи рассматриваются как битовая последовательность некоторого двоичного представления, и каждый узел с его дочерними ветвями представляет значение подпоследовательности этой битовой последовательности для формирования двоичного дерева (подпоследовательность содержит только один бит). ) или n-арное дерево (подпоследовательность содержит несколько битов).
Приведем пример, объясняющий разницу между «классическими» попытками и побитовыми попытками: для чисел в качестве ключей алфавит дерева может состоять из символов «0» .. «9», обозначающих цифры числа в десятичной системе. и узлы будут иметь до 10 возможных дочерних элементов.
Существует несколько простых подходов к реализации такого дерева, как физическая структура данных. Сформулирую два:
- Узел может быть представлен массивом дочерних указателей для каждого символа алфавита. – массив из 10 указателей на узел в примере с десятичным числом. Это дает время поиска с длина ключа. Но это неэффективно, поскольку каждый узел сохраняет место для всех возможных дочерних символов, даже если нет ключа, реализующего этот путь.
- Узел содержит список кортежей (символ, дочерний указатель), упорядоченных по символам, что позволяет осуществлять двоичный поиск по этому списку. Это обеспечивает лучшую эффективность использования пространства, но время поиска теперь равно . Идеальное дерево имеет время доступа, не зависящее от количества хранящихся ключей.
Эти подходы ухудшаются для больших алфавитов, если, например, ключ представляет собой строку символов Юникода . Обработка ключа как битовой последовательности позволяет иметь фиксированную мощность для каждого узла.
Побитовая попытка с растровым изображением
[ редактировать ]Бэгвелл [ 1 ] представил эффективное по времени и пространству решение для попыток под названием Array Mapped Tree (AMT). Дерево , отображаемое хэш-массивом (HAMT), основано на AMT. Компактное представление узла дерева использует битовую карту для обозначения каждой допустимой ветви — побитовое дерево с битовой картой . AMT использует восемь 32-битных битовых карт на узел для представления 256-мерного дерева, которое может представлять 8-битную последовательность на узел. Вариант с 64-битными процессорами ( 64-битные вычисления ) заключается в использовании 64-мерного дерева только с одним 64-битным растровым изображением на узел, которое может представлять 6-битную последовательность.
Чтобы определить индекс дочернего указателя узла для такого заданного 6-битного значения, необходимо вычислить количество предшествующих дочерних указателей. Оказывается, это можно реализовать весьма эффективно.
Обход узла
[ редактировать ]long bitMap = mem[nodeIdx];
long bitPos = 1L << value; // 6-bit-value
if ((bitMap & bitPos) == 0)
return false; // not found
long childNodeIdx = mem[nodeIdx + 1 + Long.bitCount(bitMap & (bitPos - 1))];
Смещение для поиска индекса на основе текущего индекса узла представляет собой количество младших битов, установленных в растровом изображении перед целевой позицией, плюс один для растрового изображения. Количество набора младших битов можно эффективно вычислить с постоянной сложностью по времени, используя простые битовые операции и операцию CTPOP (подсчет популяции), которая определяет количество установленных битов, которая доступна как Long.bitCount() в Java. Сам CTPOP можно довольно эффективно реализовать с помощью «бит-хака». [ 2 ] и многие современные процессоры даже предоставляют CTPOP в качестве специальной инструкции, рассматриваемой компиляторами как встроенная функция .
Реализация бит-хака CTPOP
[ редактировать ]int bitCount(long x)
x -= ((x >>> 1) & 0x5555555555555555L);
x = (x & 0x3333333333333333L) + ((x >>> 2) & 0x3333333333333333L);
x = (x + (x >>> 4)) & 0x0f0f0f0f0f0f0f0fL;
x += (x >>> 8);
x += (x >>> 16);
x += (x >>> 32);
return x & 0x7f;
Как использовать этот принцип для универсального индекса для баз данных и приложений поиска информации , описано в разделе . [ 3 ] Специализированное и упрощенное решение, демонстрирующее эти концепции, показано ниже для реализации набора 32-битных целых чисел.
Установить пример реализации
[ редактировать ]Физическая структура данных
[ редактировать ]В этом примере реализации побитового дерева с растровым изображением узлы помещаются в массив длинных (64-битных) целых чисел. Узел идентифицируется по положению (индексу) в этом массиве. Индекс корневого узла отмечает корень дерева.
Узлы выделяются из неиспользуемого пространства в этом массиве, при необходимости расширяя массив. Кроме того, заменяемые узлы собираются в свободные списки и их пространство перерабатывается. Без этой переработки структуру данных можно использовать для реализации постоянной структуры данных, просто сохраняя предыдущий корневой индекс и никогда не переопределяя существующие узлы, но всегда создавая копию измененного узла.
Листовые узлы встроены: вместо дочернего указателя на листовой узел сохраняется растровое изображение самого листового узла.
public class BBTrieSet {
long[] mem;
long[] freeLists;
long freeIdx;
long root;
long count;
// maximum node size is 1 (bitMap) + 64 (child pointers or leaf values) + 1 as arrays are zero based
final static int FREE_LIST_SIZE = 1+64+1;
final static int KNOWN_EMPTY_NODE = 0;
final static int KNOWN_DELETED_NODE = 1;
final static int HEADER_SIZE = 2; // KNOWN_EMPTY_NODE, KNOWN_DELETED_NODE
public BBTrieSet(int size) {
mem = new long[size];
freeLists = new long[FREE_LIST_SIZE];
freeIdx = HEADER_SIZE;
root = KNOWN_EMPTY_NODE;
count = 0;
}
private long allocate(int size) {
long free = freeLists[size];
if (free != 0) {
// requested size available in free list, re-link and return head
freeLists[size] = mem[(int) free];
return free;
}
else {
// expansion required?
if (freeIdx + size > mem.length) {
// increase by 25% and assure this is enough
int currSize = mem.length;
int newSize = currSize + Math.max(currSize / 4, size);
mem = Arrays.copyOf(mem, newSize);
}
long idx = freeIdx;
freeIdx += size;
return idx;
}
}
private long allocateInsert(long nodeIdx, int size, int childIdx) {
long newNodeRef = allocate(size + 1);
int a = (int) newNodeRef;
int b = (int) nodeIdx;
// copy with gap for child
for (int j = 0; j < childIdx; j++)
mem[a++] = mem[b++];
a++; // inserted
for (int j = childIdx; j < size; j++)
mem[a++] = mem[b++];
deallocate(nodeIdx, size);
return newNodeRef;
}
private long allocateDelete(long nodeIdx, int size, int childIdx) {
long newNodeRef = allocate(size - 1);
// copy with child removed
int a = (int) newNodeRef;
int b = (int) nodeIdx;
for (int j = 0; j < childIdx; j++)
mem[a++] = mem[b++];
b++; // removed
for (int j = childIdx + 1; j < size; j++)
mem[a++] = mem[b++];
deallocate(nodeIdx, size);
return newNodeRef;
}
private void deallocate(long idx, int size) {
if (idx == KNOWN_EMPTY_NODE)
return; // keep our known empty node
// add to head of free-list
mem[(int) idx] = freeLists[size];
freeLists[size] = idx;
}
private long createLeaf(byte[] key, int off, int len) {
long newNodeRef = allocate(2);
int a = (int) newNodeRef;
mem[a++] = 1L << key[len - 2];
mem[a] = 1L << key[len - 1]; // value
len -= 3;
while (len >= off) {
long newParentNodeRef = allocate(2);
a = (int) newParentNodeRef;
mem[a++] = 1L << key[len--];
mem[a] = newNodeRef;
newNodeRef = newParentNodeRef;
}
return newNodeRef;
}
private long insertChild(long nodeRef, long bitMap, long bitPos, int idx, long value) {
int size = Long.bitCount(bitMap);
long newNodeRef = allocateInsert(nodeRef, size + 1, idx + 1);
mem[(int) newNodeRef] = bitMap | bitPos;
mem[(int) newNodeRef+ 1 + idx] = value;
return newNodeRef;
}
private long removeChild(long nodeRef, long bitMap, long bitPos, int idx) {
int size = Long.bitCount(bitMap);
if (size > 1) {
// node still has other children / leaves
long newNodeRef = allocateDelete(nodeRef, size + 1, idx + 1);
mem[(int) newNodeRef] = bitMap & ~bitPos;
return newNodeRef;
}
else {
// node is now empty, remove it
deallocate(nodeRef, size + 1);
return KNOWN_DELETED_NODE;
}
}
public long size() {
return count;
}
}
Установить операции
[ редактировать ]Содержит ключ
[ редактировать ]Метод get проверяет, является ли ключ частью набора. Ключ поставляется в виде byte[], где каждый байт представляет одну 6-битную последовательность бит ключа, поэтому используются только 6 из 8 бит на байт.
public boolean get(byte[] key, int len) {
if (root == KNOWN_EMPTY_NODE)
return false;
long nodeRef = root;
int off = 0;
for (;;) {
long bitMap = mem[(int) nodeRef];
long bitPos = 1L << key[off++]; // mind the ++
if ((bitMap & bitPos) == 0)
return false; // not found
long value = mem[(int) nodeRef + 1 + Long.bitCount(bitMap & (bitPos - 1))];
if (off == len - 1) {
// at leaf
long bitPosLeaf = 1L << key[off];
return ((value & bitPosLeaf) != 0);
}
else {
// child pointer
nodeRef = value;
}
}
}
Установить (добавить) ключ
[ редактировать ] public boolean set(byte[] key, int len) {
long nodeRef = set(root, key, 0, len);
if (nodeRef != KNOWN_EMPTY_NODE) {
// denotes change
count++;
root = nodeRef;
return true;
}
else
return false;
}
private long set(long nodeRef, byte[] key, int off, int len) {
long bitMap = mem[(int) nodeRef];
long bitPos = 1L << key[off++]; // mind the ++
int idx = Long.bitCount(bitMap & (bitPos - 1));
if ((bitMap & bitPos) == 0) {
// child not present yet
long value;
if (off == len - 1)
value = 1L << key[off];
else
value = createLeaf(key, off, len);
return insertChild(nodeRef, bitMap, bitPos, idx, value);
}
else {
// child present
long value = mem[(int) nodeRef + 1 + idx];
if (off == len - 1) {
// at leaf
long bitPosLeaf = 1L << key[off];
if ((value & bitPosLeaf) == 0) {
// update leaf bitMap
mem[(int) nodeRef + 1 + idx] = value | bitPosLeaf;
return nodeRef;
}
else
// key already present
return KNOWN_EMPTY_NODE;
}
else {
// not at leaf, recursion
long childNodeRef = value;
long newChildNodeRef = set(childNodeRef, key, off, len);
if (newChildNodeRef == KNOWN_EMPTY_NODE)
return KNOWN_EMPTY_NODE;
if (newChildNodeRef != childNodeRef)
mem[(int) nodeRef + 1 + idx] = newChildNodeRef;
return nodeRef;
}
}
}
Клавиша очистки (удаления)
[ редактировать ] public boolean clear(byte[] key, int len) {
long nodeRef = clear(root, key, 0, len);
if (nodeRef != KNOWN_EMPTY_NODE) {
count--;
if (nodeRef == KNOWN_DELETED_NODE)
root = KNOWN_EMPTY_NODE;
else
root = nodeRef;
return true;
}
else
return false;
}
public long clear(long nodeRef, byte[] key, int off, int len) {
if (root == KNOWN_EMPTY_NODE)
return KNOWN_EMPTY_NODE;
long bitMap = mem[(int) nodeRef];
long bitPos = 1L << key[off++]; // mind the ++
if ((bitMap & bitPos) == 0) {
// child not present, key not found
return KNOWN_EMPTY_NODE;
}
else {
// child present
int idx = Long.bitCount(bitMap & (bitPos - 1));
long value = mem[(int) nodeRef + 1 + idx];
if (off == len - 1) {
// at leaf
long bitPosLeaf = 1L << key[off];
if ((value & bitPosLeaf) == 0)
// key not present
return KNOWN_EMPTY_NODE;
else {
// clear bit in leaf
value = value & ~bitPosLeaf;
if (value != 0) {
// leaf still has some bits set, keep leaf but update
mem[(int) nodeRef + 1 + idx] = value;
return nodeRef;
}
else
return removeChild(nodeRef, bitMap, bitPosLeaf, idx);
}
}
else {
// not at leaf
long childNodeRef = value;
long newChildNodeRef = clear(childNodeRef, key, off, len);
if (newChildNodeRef == KNOWN_EMPTY_NODE)
return KNOWN_EMPTY_NODE;
if (newChildNodeRef == KNOWN_DELETED_NODE)
return removeChild(nodeRef, bitMap, bitPos, idx);
if (newChildNodeRef != childNodeRef)
mem[(int) nodeRef + 1 + idx] = newChildNodeRef;
return nodeRef;
}
}
}
}
Операторы установки
[ редактировать ]Операторы множества для пересечения (и), объединения (или) и разницы (минус) возможны с использованием шаблона-легковеса, как показано ниже.
Интерфейс представляет собой физические узлы и «виртуальные» узлы результатов оператора. Экземпляры этого интерфейса создаются по требованию во время обхода дерева. Составные выражения, включающие более одного оператора, могут быть выражены напрямую путем объединения этих операторов, поскольку оператор может использоваться в качестве аргумента (входа) для другого оператора.
Интерфейс легковеса
[ редактировать ]public interface BBTrieNode {
public long getBitMap();
public long getBitMapLeaf(long bitPos);
public BBTrieNode getChildNode(long bitPos);
}
public static class BBTrieNodeMem implements BBTrieNode {
long nodeRef;
long[] mem;
BBTrieNodeMem child;
public BBTrieNodeMem(long nodeRef, long[] mem) {
this.nodeRef = nodeRef;
this.mem = mem;
}
@Override
public long getBitMap() {
return mem[(int) nodeRef];
}
@Override
public long getBitMapLeaf(long bitPos) {
int idx = Long.bitCount(getBitMap() & (bitPos - 1));
long value = mem[(int) nodeRef + 1 + idx];
return value;
}
@Override
public BBTrieNode getChildNode(long bitPos) {
int idx = Long.bitCount(getBitMap() & (bitPos - 1));
long value = mem[(int) nodeRef + 1 + idx];
return new BBTrieNodeMem(value, mem);
}
}
Пересечение (И)
[ редактировать ]Оператор пересечения очень эффективен, поскольку он автоматически выполняет обрезку даже подвыражений. Доступ к нерелевантным дочерним узлам не требуется, поскольку растровое изображение и побитовая операция И позволяют заранее определить результат. Например, вычисление , подвыражение не будет материализован как промежуточный результат.
public static class BBTrieAnd implements BBTrieNode {
BBTrieNode nodeA;
BBTrieNode nodeB;
long bitMapA;
long bitMapB;
public BBTrieAnd(BBTrieNode nodeA, BBTrieNode nodeB) {
this.nodeA = nodeA;
this.nodeB = nodeB;
bitMapA = nodeA.getBitMap();
bitMapB = nodeB.getBitMap();
}
public long getBitMap() {
return bitMapA & bitMapB; // this gives a nice optimization (pruning)
}
public long getBitMapLeaf(long bitPos) {
return nodeA.getBitMapLeaf(bitPos) & nodeB.getBitMapLeaf(bitPos);
}
public BBTrieNode getChildNode(long bitPos) {
BBTrieNode childNodeA = nodeA.getChildNode(bitPos);
BBTrieNode childNodeB = nodeB.getChildNode(bitPos);
return new BBTrieAnd(childNodeA, childNodeB);
}
}
Союз (Орегон)
[ редактировать ]public static class BBTrieOr implements BBTrieNode {
BBTrieNode nodeA;
BBTrieNode nodeB;
long bitMapA;
long bitMapB;
public BBTrieOr(BBTrieNode nodeA, BBTrieNode nodeB) {
this.nodeA = nodeA;
this.nodeB = nodeB;
bitMapA = nodeA.getBitMap();
bitMapB = nodeB.getBitMap();
}
public long getBitMap() {
return bitMapA | bitMapB;
}
public long getBitMapLeaf(long bitPos) {
return nodeA.getBitMapLeaf(bitPos) | nodeB.getBitMapLeaf(bitPos);
}
public BBTrieNode getChildNode(long bitPos) {
if ((bitMapA & bitPos) != 0) {
BBTrieNode childNodeA = nodeA.getChildNode(bitPos);
if ((bitMapB & bitPos) != 0) {
BBTrieNode childNodeB = nodeB.getChildNode(bitPos);
return new BBTrieOr(childNodeA, childNodeB);
}
else
return childNodeA; // optimization, no more or-node required
}
else {
BBTrieNode childNodeB = nodeB.getChildNode(bitPos);
return childNodeB; // optimization, no more or-node required
}
}
}
Разница (МИНУС)
[ редактировать ]public static class BBTrieMinus implements BBTrieNode {
BBTrieNode nodeA;
BBTrieNode nodeB;
long bitMapA;
long bitMapB;
public BBTrieMinus(BBTrieNode nodeA, BBTrieNode nodeB) {
this.nodeA = nodeA;
this.nodeB = nodeB;
bitMapA = nodeA.getBitMap();
bitMapB = nodeB.getBitMap();
}
public long getBitMap() {
return bitMapA; // bitMapB not useful here
}
public long getBitMapLeaf(long bitPos) {
long childBitMapA = nodeA.getBitMapLeaf(bitPos);
if ((bitMapB & bitPos) == 0)
return childBitMapA;
long childBitMapB = nodeB.getBitMapLeaf(bitPos);
return childBitMapA & ~childBitMapB;
}
public BBTrieNode getChildNode(long bitPos) {
BBTrieNode childNodeA = nodeA.getChildNode(bitPos);
if ((bitMapB & bitPos) == 0)
return childNodeA; // optimization, no more minus-node required
BBTrieNode childNodeB = nodeB.getChildNode(bitPos);
return new BBTrieMinus(childNodeA, childNodeB);
}
}
Диапазоны
[ редактировать ]Используя подход виртуального узла, запросы диапазона могут быть выполнены путем пересечения виртуального дерева, генерирующего диапазон (см. ниже), с другим оператором. Итак, чтобы определить, какие числа набора, скажем, , лежат в определенном диапазоне, скажем, [10..50], вместо того, чтобы перебирать набор и проверять каждую запись, это выполняется путем оценки .
public static class BBTrieIntRange implements BBTrieNode {
private long bitMap;
private int a, b;
private int x, y;
private int level;
public BBTrieIntRange(int a, int b) {
this(a, b, 5);
}
private BBTrieIntRange (int a, int b, int level) {
this.a = a;
this.b = b;
this.level = level;
x = (int) (a >>> (level * 6)) & 0x3F;
y = (int) (b >>> (level * 6)) & 0x3F;
// bit hack for: for (int i = x; i <= y; i++) bitSet |= (1L << i);
bitMap = 1L << y;
bitMap |= bitMap - 1;
bitMap &= ~((1L << x) - 1);
}
public long getBitMap() {
return bitMap;
}
public long getBitMapLeaf(long bitPos) {
// simple solution for readability (not that efficient as for each call a child is created again)
return getChildNode(bitPos).getBitMap();
}
public BBTrieIntRange getChildNode(long bitPos) {
int bitNum = Long.numberOfTrailingZeros(bitPos);
if (x == y)
return new BBTrieIntRange(a, b, level - 1);
else if (bitNum == x)
return new BBTrieIntRange(a, ~0x0, level - 1);
else if (bitNum == y)
return new BBTrieIntRange(0, b, level - 1);
else
return new BBTrieIntRange(0, ~0x0, level - 1);
}
}
Пример использования
[ редактировать ]В примере показано использование 32-битных целых чисел в качестве ключей.
public class BBTrieSetSample {
public interface Visitor {
public void visit(byte[] key, int keyLen);
}
public static void visit(BBTrieNode node, Visitor visitor, byte[] key, int off, int len) {
long bitMap = node.getBitMap();
if (bitMap == 0)
return;
long bits = bitMap;
while (bits != 0) {
long bitPos = bits & -bits; bits ^= bitPos; // get rightmost bit and clear it
int bitNum = Long.numberOfTrailingZeros(bitPos);
key[off] = (byte) bitNum;
if (off == len - 2) {
long value = node.getBitMapLeaf(bitPos);
long bits2 = value;
while (bits2 != 0) {
long bitPos2 = bits2 & -bits2; bits2 ^= bitPos2;
int bitNum2 = Long.numberOfTrailingZeros(bitPos2);
key[off+1] = (byte) bitNum2;
visitor.visit(key, off + 2);
}
}
else {
BBTrieNode childNode = node.getChildNode(bitPos);
visit(childNode, visitor, key, off + 1, len);
}
}
}
public static int set6Int(byte[] b, int value) {
int pos = 0;
b[pos ] = (byte) ((value >>> 30) & 0x3F);
b[pos + 1] = (byte) ((value >>> 24) & 0x3F);
b[pos + 2] = (byte) ((value >>> 18) & 0x3F);
b[pos + 3] = (byte) ((value >>> 12) & 0x3F);
b[pos + 4] = (byte) ((value >>> 6) & 0x3F);
b[pos + 5] = (byte) (value & 0x3F);
return 6;
}
public static int get6Int(byte[] b) {
int pos = 0;
return
((b[pos ] & 0x3F) << 30) |
((b[pos + 1] & 0x3F) << 24) |
((b[pos + 2] & 0x3F) << 18) |
((b[pos + 3] & 0x3F) << 12) |
((b[pos + 4] & 0x3F) << 6) |
(b[pos + 5] & 0x3F);
}
public static void main(String[] args) {
BBTrieSet trie1 = new BBTrieSet(100);
BBTrieSet trie2 = new BBTrieSet(100);
byte[] key = new byte[64];
int len;
final int KEY_LEN_INT = set6Int(key, 1); // 6
int[] test = new int[] { 10, 20, 30, 40, 50, 30, 60, 61, 62, 63 };
for (int i = 0; i < test.length; i++) {
len = set6Int(key, test[i]);
boolean change = trie1.set(key, len);
System.out.println("set: " + test[i] + ", " + change);
}
System.out.println("trie1 size: " + trie1.size());
BBTrieSetOps.visit(new BBTrieNodeMem(trie1.root, trie1.mem), new BBTrieSetOps.Visitor() {
@Override
public void visit(byte[] key, int keyLen) {
System.out.println("Visitor: "+ get6Int(key) + ", " + keyLen);
}
}, key, 0, KEY_LEN_INT);
test = new int[] { 10, 25, 30, 40, 45, 50, 55, 60 };
for (int i = 0; i < test.length; i++) {
len = set6Int(key, test[i]);
boolean contained = trie1.get(key, len);
System.out.println("contained: " + test[i] + ", " + contained);
}
test = new int[] { 10, 20, 30, 40, 45, 50, 55, 60, 61, 62, 63 };
for (int i = 0; i < test.length; i++) {
len = set6Int(key, test[i]);
boolean change = trie1.clear(key, len);
System.out.println("cleared: " + test[i] + ", " + change);
BBTrieSetOps.visit(new BBTrieNodeMem(trie1.root, trie1.mem), new BBTrieSetOps.Visitor() {
@Override
public void visit(byte[] key, int keyLen) {
System.out.print(get6Int(key) + " ");
}
}, key, 0, KEY_LEN_INT);
System.out.println();
}
System.out.println("trie1 size: " + trie1.size());
for (int i = 0; i <= 50; i++) {
len = set6Int(key, i);
trie1.set(key, len);
System.out.println("set: " + i);
}
System.out.println("trie1 size: " + trie1.size());
for (int i = 25; i <= 75; i++) {
len = set6Int(key, i);
trie2.set(key, len);
System.out.println("set: " + i);
}
System.out.println("trie2 size: " + trie2.size());
// AND example
BBTrieNode result = new BBTrieAnd(
new BBTrieNodeMem(trie1.root, trie1.mem),
new BBTrieNodeMem(trie2.root, trie2.mem));
BBTrieSetOps.visit(result, new BBTrieSetOps.Visitor() {
@Override
public void visit(byte[] key, int keyLen) {
System.out.println("Visitor AND result: " + get6Int(key));
}
}, key, 0, KEY_LEN_INT);
}
}
Ссылки
[ редактировать ]- ^ Фил Бэгвелл (2000). Быстрая и эффективная сортировка поиска (PDF) (Отчет). Факультет информационных наук Федеральной политехнической школы Лозанны .
- ^ Уоррен младший, Генри С. (2013). Хакерское наслаждение (2-е изд.). Аддисон Уэсли - Pearson Education, Inc. ISBN 978-0-321-84268-8 .
- ^ Патент EP 3376407 , Вальтер Бауэр, «Эффективное использование древовидной структуры данных в базах данных», опубликован 19 сентября 2018 г., выдан 16 сентября 2020 г., передан censhare AG.