B-drzewo

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania
B-tree-definition.png

B-drzewodrzewiasta struktura danych, przechowująca klucze w pewnym porządku i powiązane z nimi dane, używana przede wszystkim w systemach baz danych.

DVD (Digital Video Disc lub Digital Versatile Disc) – rozpowszechniony w roku 1995 standard zapisu danych na optycznym nośniku danych, podobnym do CD-ROM (te same wymiary: 12 lub 8 cm) lecz o większej pojemności uzyskanej dzięki zwiększeniu gęstości zapisu.2-3 drzewem nazywamy strukturę danych będącą B-drzewem, w którym każdy wierzchołek z potomkami posiada albo 2 potomków i jeden element z informacją lub 3 potomków i 2 elementy z informacją. Wszystkie wierzchołki nie posiadające następników (liście) znajdują się na jednym poziomie. Informacje zachowywane są w pewnym porządku. Drzewa takie są zawsze zbalansowane, co gwarantuje logarytmiczny (względem rozmiaru) czas wykonywania podstawowych operacji (wstawianie, wyszukiwanie, usuwanie elementów).

Głównym pomysłem zastosowanym w B-drzewach jest struktura wewnętrznego węzła. Każdy węzeł może posiadać od do węzłów potomnych, gdzie to rząd B-drzewa; wyjątkiem jest korzeń, który może posiadać od do węzłów potomnych. Te założenia gwarantują, że wysokość drzewa zawierającego kluczy będzie niska, rzędu co też powoduje, że asymptotyczna złożoność czasowa operacji podstawowych: wyszukiwania, wstawiania i kasowania kluczy jest rzędu

Asymptotyczne tempo wzrostu jest miarą określającą zachowanie wartości funkcji wraz ze wzrostem jej argumentów. Stosowane jest szczególnie często w teorii obliczeń, w celu opisu złożoności obliczeniowej, czyli zależności ilości potrzebnych zasobów (np. czasu lub pamięci) od rozmiaru danych wejściowych algorytmu. Asymptotyczne tempo wzrostu opisuje jak szybko dana funkcja rośnie lub maleje, abstrahując od konkretnej postaci tych zmian.Struktura danych (ang. data structure) - sposób uporządkowania informacji w komputerze. Na strukturach danych operują algorytmy.

Niska wysokość drzewa powoduje, że liczba węzłów, które trzeba odczytać bądź zapisać, jest niewielka. W praktycznych zastosowaniach, w których informacje przechowywane są na dyskach twardych bądź płytach CD/DVD ma to fundamentalne znaczenie, bowiem czasy dostępu do tych urządzeń są dużo większe niż do pamięci wewnętrznej komputera i dominują w całkowitym czasie wykonywania operacji na danych (czasy dostępu do pamięci komputera rzędu mikro- lub setek nanosekund, natomiast do współczesnych dysków twardych to kilka milisekund – czyli 3–4 rzędy wielkości więcej). Z kolei zlokalizowanie odpowiedniego klucza bądź potomka w węźle wczytanym do pamięci wewnętrznej jest dużo szybsze, nawet jeśli rząd drzewa jest duży.

System plików – metoda przechowywania plików, zarządzania plikami, informacjami o tych plikach, tak by dostęp do plików i danych w nich zgromadzonych był łatwy dla użytkownika systemu; także: wolumin.Płyta kompaktowa (ang. Compact Disc, CD-ROM – Compact Disc – Read Only Memory) — poliwęglanowy krążek z zakodowaną cyfrowo informacją do bezkontaktowego odczytu światłem lasera optycznego. Zaprojektowany w celu nagrywania i przechowywania dźwięku, przy użyciu kodowania PCM, który dzisiaj jest tylko jednym ze standardów cyfrowego zapisu dźwięku. Taką płytę nazywa się CD-Audio. Dzięki dużej jak na swoje czasy pojemności, niezawodności i niskiej cenie, dysk kompaktowy stał się popularnym medium do zapisywania danych.

B+drzewo[ | edytuj kod]

Popularniejsze w zastosowaniach bazodanowych i systemach plikówB+drzewa, które są szczególnym przypadkiem B-drzew, przechowującym dane tylko w liściach.

Baza danych – zbiór danych zapisanych zgodnie z określonymi regułami. W węższym znaczeniu obejmuje dane cyfrowe gromadzone zgodnie z zasadami przyjętymi dla danego programu komputerowego specjalizowanego do gromadzenia i przetwarzania tych danych. Program taki (często pakiet programów) nazywany jest „systemem zarządzania bazą danych” (ang. database management system, DBMS).Dysk twardy, napęd dysku twardego (ang. hard disk drive) – rodzaj pamięci masowej, wykorzystujący nośnik magnetyczny do przechowywania danych. Nazwa "dysk twardy" wynika z zastosowania twardego materiału jako podłoża dla właściwego nośnika, w odróżnieniu od dyskietek (ang. floppy disk, czyli miękki dysk), w których nośnik magnetyczny naniesiono na podłoże elastyczne.


Podstrony: 1 [2] [3]




Reklama