GoSuda

Bitmap Animasi

By snowmerak
views ...

Apa itu Bitmap?

Bitmap di sini adalah salah satu jenis index. Jika Anda datang dengan pemikiran grafis, Anda dapat menekan tombol kembali.

Konsep Dasar

Bitmap adalah salah satu bentuk teknologi indexing dalam basis data. Ini merepresentasikan nilai dari kolom tertentu sebagai elemen atau bentuk dari array bit atau vektor, di mana setiap bit menunjukkan keberadaan atau ketiadaan nilai tertentu dalam kolom tersebut. Oleh karena itu, bentuk paling dasar adalah menetapkan index bit untuk setiap baris dan merepresentasikan keberadaan dengan 0 dan ketiadaan dengan 1.

Sebagai contoh, mari kita asumsikan ada sebuah tabel dengan kolom jenis kelamin. Tabel ini memiliki 5 baris, dan nilai kolom jenis kelamin adalah sebagai berikut:

  1. Pria
  2. Wanita
  3. Pria
  4. Wanita
  5. Lain-lain

Dalam kasus ini, index bitmap untuk kolom jenis kelamin dapat direpresentasikan sebagai berikut:

  • Pria: 10100
  • Wanita: 01010
  • Lain-lain: 00001

Jadi, di mana sebenarnya ini digunakan?

Jadi, semua orang mungkin berpikir bahwa ini bukan hanya untuk merepresentasikan hal tersebut. Untuk menggunakan index bitmap dengan benar, mari kita pertimbangkan kasus berikut.

1CREATE TABLE IF NOT EXISTS Users (
2    id INT PRIMARY KEY,
3    name VARCHAR(100),
4    active BOOLEAN,
5    sex BOOLEAN,
6    age INT
7);

Asumsikan tabel ini memiliki 1.000.000 baris. Dan mari kita asumsikan kita menjalankan kueri berikut.

1SELECT * FROM Users WHERE active = TRUE AND SEX = TRUE;

Kueri ini mencari baris di mana kolom active dan sex keduanya TRUE. Maka, cara tercepat untuk menemukan baris yang memenuhi kondisi kedua kolom TRUE adalah dengan memanfaatkan operasi bit AND.

  • Asumsikan index bitmap untuk kolom active telah di-indexing sebelumnya sebagai 1100110011... (array bit 1.000.000), dan
  • Asumsikan index bitmap untuk kolom sex telah di-indexing sebelumnya sebagai 1010101010... (array bit 1.000.000).

Maka, dengan melakukan operasi bit AND pada kedua index bitmap, kita dapat dengan cepat menemukan baris di mana kedua kolom adalah TRUE. Karena ini adalah operasi bit sederhana, hasilnya akan diperoleh jauh lebih cepat daripada pemindaian index lainnya.

Trade-off

Index bitmap bisa sangat efisien, tetapi ada beberapa trade-off. Meskipun ada banyak kekurangan lain, untuk saat ini kita hanya akan membahas satu.

Yaitu, index bitmap lebih cocok untuk kardinalitas rendah (yaitu, ketika jumlah nilai yang mungkin dalam kolom sedikit). Menggunakan index bitmap pada kolom dengan kardinalitas tinggi dapat menyebabkan bitmap menjadi sangat besar.

Jika index bitmap digunakan pada kolom dengan kardinalitas tinggi, mungkin diperlukan banyak ruang penyimpanan karena bitmap terpisah harus dibuat untuk setiap nilai unik. Misalnya, jika ada 1.000.000 nilai unik dalam kolom, 1.000.000 bitmap harus dibuat, yang bisa sangat tidak efisien.

Jadi, kami

Untuk menggantikan bitmap yang berasal dari kardinalitas tinggi, kita dapat menggunakan Roaring Bitmap. Roaring Bitmap memiliki beberapa karakteristik, tetapi filosofi dan karakteristik dasar terbesarnya adalah secara dinamis memilih metode penyimpanan yang paling sesuai berdasarkan kepadatan data untuk memaksimalkan rasio kompresi dan kecepatan operasi.

Konsep Dasar Roaring Bitmap

Indexing 2 Tahap

Untuk menyimpan satu bilangan bulat, Roaring Bitmap pertama-tama melalui 2 tahap berikut. Ini disebut indexing 2 tahap, tetapi Anda bisa menganggapnya sebagai array 2 dimensi.

  • Ekstraksi 16 bit atas: Ekstrak 16 bit atas dari bilangan bulat dan gunakan sebagai index. Ini akan menjadi index dari array luar di antara array 2 dimensi dengan panjang total 65536. Array ini menyimpan alamat kontainer yang akan dijelaskan nanti.
  • Ekstraksi 16 bit bawah: Ekstrak 16 bit bawah dari bilangan bulat dan gunakan sebagai posisi di dalam kontainer.

Kontainer

Kontainer ini sesuai dengan array bagian dalam di antara array 2 dimensi, seperti yang saya analogikan sebelumnya. Namun, tidak seperti 16 bit atas, struktur internal kontainer ini bervariasi tergantung pada seberapa banyak data internal yang ada. Roaring Bitmap mendukung 3 kontainer berikut:

  • Array Container: Kontainer ini digunakan ketika data yang disimpan di dalamnya sedikit. Secara spesifik, ini digunakan untuk menyimpan 4096 elemen atau kurang. Kontainer ini diimplementasikan sebagai array bilangan bulat yang diurutkan. Elemen dapat ditemukan dengan pencarian biner.
  • Bitmap Container: Kontainer ini digunakan ketika data yang disimpan di dalamnya banyak. Secara spesifik, ini digunakan untuk menyimpan lebih dari 4096 elemen. Kontainer ini diimplementasikan sebagai bitmap 65536 bit (8192 byte). Setiap bit menunjukkan apakah bilangan bulat pada posisi tersebut ada atau tidak.
  • Run Container: Kontainer ini digunakan untuk menyimpan rentang bilangan bulat yang berurutan. Misalnya, efisien untuk menyimpan bilangan bulat berurutan seperti 1, 2, 3, 4, 5. Kontainer ini diimplementasikan sebagai daftar pasangan (nilai awal, panjang). Jika semuanya ada? Itu berarti semuanya ada dari awal hingga akhir, jadi kita hanya perlu menyimpan satu (0, 65536).

Pendekatan ini memungkinkan Roaring Bitmap untuk menggunakan memori secara sangat efisien dan memberikan kinerja optimal untuk berbagai kepadatan data.

Fungsionalitas Roaring Bitmap

Fungsionalitas Dasar

Roaring Bitmap menyediakan fungsionalitas dasar berikut:

  • Penyisipan: Menambahkan bilangan bulat baru ke bitmap. Selama proses ini, kontainer yang sesuai dapat dipilih atau kontainer dapat diubah sesuai kebutuhan.
  • Penghapusan: Menghapus bilangan bulat yang ada dari bitmap. Selama proses ini, penanganan yang sesuai dilakukan tergantung pada status kontainer.
  • Pencarian: Memverifikasi apakah bilangan bulat tertentu ada di bitmap. Proses ini dilakukan dengan sangat cepat.

Operasi Himpunan

Roaring Bitmap juga mendukung operasi himpunan berikut:

  • Union: Membuat bitmap baru yang berisi semua elemen dari dua bitmap.
  • Intersection: Membuat bitmap baru yang hanya berisi elemen yang ada di kedua bitmap.
  • Symmetric Difference: Membuat bitmap baru yang berisi elemen yang hanya ada di salah satu dari dua bitmap.

Operasi-operasi ini dioptimalkan dan dilakukan dengan sangat cepat tergantung pada jenis kontainer bitmap.

Dalam Bahasa Go

Dalam bahasa Go, Anda dapat dengan mudah menggunakan Roaring Bitmap dengan menggunakan paket github.com/RoaringBitmap/roaring. Paket ini menyediakan semua fungsionalitas Roaring Bitmap dan dioptimalkan agar sesuai dengan karakteristik bahasa Go.

Instalasi

1go get github.com/RoaringBitmap/roaring/v2

Contoh Penggunaan

 1package main
 2
 3import (
 4	"log"
 5
 6	"github.com/RoaringBitmap/roaring/v2"
 7)
 8
 9func main() {
10	b1 := roaring.BitmapOf(1, 2, 3, 4)     // Inisialisasi dengan 1, 2, 3, 4
11	b2 := roaring.BitmapOf(2, 4, 6, 8, 12) // Inisialisasi dengan 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Tambahkan 5
14	b2.Add(10) // Tambahkan 10
15
16	b2.Remove(12) // Hapus 12
17
18	and := roaring.FastAnd(b1, b2)
19	or := roaring.FastOr(b1, b2)
20
21	// Operasi bitmap mengubah yang asli, jadi gunakan klon
22	xor := b1.Clone()
23	xor.Xor(b2)
24
25	log.Printf("and result: %v", and.ToArray())
26	log.Printf("or result: %v", or.ToArray())
27	log.Printf("xor result: %v", xor.ToArray())
28}

12025/09/08 22:16:27 and result: [2 4]
22025/09/08 22:16:27 or result: [1 2 3 4 5 6 8 10]
32025/09/08 22:16:27 xor result: [1 3 5 6 8 10]

Fungsi utama yang tidak muncul dalam contoh kode di atas adalah:

  • Contains(x uint32) bool: Memverifikasi apakah nilai tertentu ada di bitmap.
  • GetCardinality() uint64: Mengembalikan jumlah elemen yang terkandung dalam bitmap.
  • Rank(x uint32) uint64: Mengembalikan jumlah elemen kurang dari atau sama dengan nilai tertentu.
  • ToBytes() ([]byte, error): Menserialisasikan bitmap ke dalam slice byte.
  • FromBytes(data []byte) error: Mengembalikan bitmap dari slice byte.
  • Clone() *Bitmap: Membuat salinan bitmap.
  • Clear(): Menginisialisasi bitmap.
  • NextValue(x uint32) int64: Mengembalikan elemen berikutnya yang lebih besar dari atau sama dengan x.
  • PreviousValue(x uint32) int64: Mengembalikan elemen sebelumnya yang lebih kecil dari x.
  • Maximum() uint32: Mengembalikan elemen terbesar dalam bitmap.
  • Minimum() uint32: Mengembalikan elemen terkecil dalam bitmap.

Fungsionalitas ini tersedia. Untuk detail lebih lanjut, silakan lihat dokumentasi resmi.

Sebagai catatan, paket roaring tidak hanya mendukung uint32 tetapi juga menyertakan paket yang mendukung uint64. Karena menyediakan antarmuka yang hampir sama, Anda dapat langsung menggantinya.

 1package main
 2
 3import (
 4	"log"
 5
 6	"github.com/RoaringBitmap/roaring/v2/roaring64"
 7)
 8
 9func main() {
10	b1 := roaring64.BitmapOf(1, 2, 3, 4)     // Inisialisasi dengan 1, 2, 3, 4
11	b2 := roaring64.BitmapOf(2, 4, 6, 8, 12) // Inisialisasi dengan 2, 4, 6, 8, 12
12
13	b1.Add(5)  // Tambahkan 5
14	b2.Add(10) // Tambahkan 10
15
16	b2.Remove(12) // Hapus 12
17
18	and := roaring64.FastAnd(b1, b2)
19	or := roaring64.FastOr(b1, b2)
20
21	// Operasi bitmap mengubah yang asli, jadi gunakan klon
22	xor := b1.Clone()
23	xor.Xor(b2)
24
25	log.Printf("and result: %v", and.ToArray())
26	log.Printf("or result: %v", or.ToArray())
27	log.Printf("xor result: %v", xor.ToArray())
28}

Kesimpulan

Roaring Bitmap adalah alat yang ampuh yang dapat menyimpan dan memanipulasi kumpulan bilangan bulat kardinalitas tinggi secara efisien. Dalam bahasa Go, dengan menggunakan paket github.com/RoaringBitmap/roaring, semua fungsionalitas Roaring Bitmap dapat dengan mudah dimanfaatkan. Paket ini memaksimalkan penggunaan memori dan kinerja melalui berbagai jenis kontainer dan operasi yang dioptimalkan. Pemrosesan data yang efisien dapat diimplementasikan dengan memanfaatkan Roaring Bitmap di berbagai bidang seperti pengindeksan basis data, analisis log, dan perhitungan statistik.

Roaring Bitmap khususnya menunjukkan kinerja tinggi pada kumpulan data besar dan dapat digunakan secara berguna dalam berbagai aplikasi. Dikombinasikan dengan sintaks Go yang ringkas dan efisien, Roaring Bitmap menyediakan alat yang ampuh bagi para pengembang. Diharapkan bahwa dengan perkembangan Roaring Bitmap di masa depan, lebih banyak fungsionalitas dan optimasi akan tercapai.

Mengapa saya melakukan ini? Untuk pengindeksan berdasarkan tag dan operasi union yang cepat dalam database deret waktu.